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
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 (lowIndexLad 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 jNu 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:
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.