Sådan implementeres QuickSort i Java?

Denne artikel introducerer dig en anden Divide And Conquer sorteringsalgoritme, der er QuickSort i Java, og følger den op med en demonstration.

QuickSort er en opdelings- og erobringsalgoritme. I Divide & Conquer algoritmedesignparadigme deler vi problemerne i delproblemer rekursivt og løser derefter delproblemerne og kombinerer endelig løsningerne for at finde det endelige resultat. I denne artikel vil vi fokusere på QuickSort In



Følgende punkter vil blive dækket i denne artikel,



Lad os begynde!

En ting at huske på, når man deler problemerne i underproblemer, er at strukturen af ​​underproblemer ikke ændres i forhold til det oprindelige problem.
Divide & Conquer-algoritmen har 3 trin:



  • Opdel: Opdel problemet i delproblemer
  • Conquer: Løs rekursivt delproblemer
  • Kombiner: Kombiner løsningerne for at få det endelige resultat

Billede - Hurtig sortering i Java- Edureka

binær søgealgoritme i java

Der er forskellige algoritmer baseret på divide & conquer paradigm. Hurtig sortering og flet sortering er blandt dem.

Selvom QuickSort's worst-case tidskompleksitet er O (n2), som er mere end mange andre sorteringsalgoritmer som Merge Sort og Heap Sort, er QuickSort hurtigere i praksis, fordi dens indre sløjfe kan implementeres effektivt på de fleste arkitekturer og i de fleste virkelige data.



Lad os tale om implementeringen af ​​hurtig sorteringsalgoritme. Quicksort-algoritmer tager et pivot-element og partitionerer arrayet omkring pivot-elementet. Der er mange variationer af Quicksot, der afhænger af, hvordan du vælger drejelementet. Der er flere måder at vælge drejelementet på:

  • Valg af det første element
  • Vælg det sidste element
  • Valg af et tilfældigt element
  • Plukker medianelement

Den næste vigtige ting at forstå er, at funktionen partition () er i hurtig sorteringsalgoritme. Partitionsfunktion for at tage et drejelement, placerer det i den rigtige position, flytter alle elementerne mindre end drejelementet til venstre og alle elementerne større til højre. Quicksort tager lineær tid at gøre det.
Derefter er arrayet opdelt i to dele fra pivotelementet (dvs. elementer mindre end pivot & elementer større end pivot), og begge arrays sorteres rekursivt ved hjælp af Quicksort-algoritme.

Nu hvor vi forstår, hvordan QuickSort-algoritmen fungerer. Lad os forstå, hvordan man implementerer Quicksort-algoritme i Java.

QuickSort Fungere:

/ * Quicksort-funktion skal matrixen sorteres med det laveste og højeste indeks * /

ugyldig sortering (int arr [], int lowIndex, int highIndex) {// Indtil lowIndex = highIndex hvis (lowIndex

Lad os nu se på partitioneringskoden for at forstå, hvordan den fungerer.

Skillevæg Kode

I partitioneringskoden vælger vi det sidste element som drejelementet. Vi krydser det komplette array (dvs. ved hjælp af variabel j i vores tilfælde). Vi holder styr på det sidste mindste element i arrayet (dvs. ved hjælp af variabel i i vores tilfælde). Hvis vi finder et element, der er mindre end omdrejningspunktet, flytter vi det aktuelle element a [j] med arr [i], ellers fortsætter vi med at krydse.

int partition (int arr [], int lowIndex, int highIndex) {// Oprettelse af det sidste element som pivot int pivot = arr [highIndex] // Brug af i til at holde styr på mindre elementer fra pivot int i = (lowIndex-1) for (int j = lowIndex j

Nu hvor du har forstået Quicksort & partitionsfunktion, lad os hurtigt se på den komplette kode

QuickSort Java-kode

klasse QuickSort {// Partition Method int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j

// Sorteringsmetode

ugyldig sortering (int arr [], int lowIndex, int highIndex) {if (lowIndex

// Metode til udskrivning af matrix

statisk ugyldig printArray (int arr []) {int n = arrlængde for (int i = 0 i

// Hovedmetode

offentlig statisk ugyldig hoved (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr. længde QuickSort ob = ny QuickSort () ob.sort (arr, 0, n-1) System.out.println ('sorteret array') printArray (arr)}}

Produktion:

Output- Hurtig sortering i Java- Edureka

Efter at have udført ovenstående Java-program, ville du have forstået, hvordan QuickSort fungerer, og hvordan man implementerer det i Java.Således er vi nået til slutningen af ​​denne artikel om 'Quicksort in Java'. Hvis du ønsker at lære mere,tjek den af Edureka, et betroet online læringsfirma. Edurekas Java J2EE- og SOA-uddannelses- og certificeringskursus er designet til at træne dig til både kerne- og avancerede Java-koncepter sammen med forskellige Java-rammer som Hibernate & Spring.

Har du et spørgsmål til os? Nævn det i kommentarsektionen på denne blog, og vi vender tilbage til dig hurtigst muligt.