streamalism.org

1. Oversigt

I denne vejledning undersøger vi QuickSort-algoritmen i detaljer og fokuserer på dens Java-implementering.

Vi diskuterer også fordelene og ulemperne og analyserer dens tidskompleksitet.

2. QuickSort-algoritme

Quicksort er en sorteringsalgoritme, der udnytter divide-and-conquer-princippet. Det har et gennemsnit O (n log n) kompleksitet, og det er en af ​​de mest anvendte sorteringsalgoritmer, især for store datamængder.

Det er vigtigt at huske, at Quicksort ikke er en stabil algoritme. En stabil sorteringsalgoritme er en algoritme, hvor elementerne med de samme værdier vises i samme rækkefølge i det sorterede output, som de vises på inputlisten.

Inputlisten er opdelt i to underlister med et element kaldet pivot; en underliste med elementer mindre end pivot og en anden med elementer større end pivot. Denne proces gentages for hver underliste.

Endelig flettes alle sorterede underlister for at danne det endelige output.

2.1. Algoritmetrin

1. Vi vælger et element fra listen, kaldet pivot. Vi bruger den til at opdele listen i to underlister.
2. Vi omarrangerer alle elementerne omkring drejningen - dem med mindre værdi placeres foran den, og alle elementerne er større end drejningen efter den. Efter dette trin er drejetappen i sin endelige position. Dette er det vigtige partitionstrin.
3. Vi anvender ovenstående trin rekursivt på begge underlister til venstre og højre for omdrejningspunktet.

Som vi kan se, quicksort er naturligvis en rekursiv algoritme, ligesom enhver tilgang og opdeling.

Lad os tage et simpelt eksempel for bedre at forstå denne algoritme.

Arr [] = {5, 9, 4, 6, 5, 3}

1. Lad os antage, at vi vælger 5 som omdrejningspunkt for enkelhed
2. Vi sætter først alle elementer mindre end 5 i matrixens første position: {3, 4, 5, 6, 5, 9}
3. Vi gentager det derefter for det venstre underarray {3,4} og tager 3 som omdrejningspunkt
4. Der er ingen elementer mindre end 3
5. Vi anvender quicksort på underarrayet til højre for pivoten, dvs. {4}
6. Denne undergruppe består kun af et sorteret element
7. Vi fortsætter med den rigtige del af det oprindelige array, {6, 5, 9}, indtil vi får den endelige ordnede array

2.2. Valg af den optimale drejning

Det afgørende punkt i QuickSort er at vælge den bedste drejning. Det midterste element er selvfølgelig det bedste, da det vil opdele listen i to lige store underlister.

Men at finde det midterste element fra en ikke-ordnet liste er vanskeligt og tidskrævende, det er derfor, vi tager det første element, det sidste element, medianen eller ethvert andet tilfældigt element som drejning.

3. Implementering i Java

Den første metode er quickSort () som tager parametre det array, der skal sorteres, det første og det sidste indeks. Først kontrollerer vi indekserne og fortsætter kun, hvis der stadig er elementer, der skal sorteres.

Vi får indekset over den sorterede pivot og bruger det til rekursivt at ringe skillevæg() metode med de samme parametre som quickSort () metode, men med forskellige indekser:

public void quickSort (int arr [], int start, int end) {if (begin <end) {int partitionIndex = partition (arr, start, slut); quickSort (arr, start, partitionIndex-1); quickSort (arr, partitionIndex + 1, slut); }}

Lad os fortsætte med skillevæg() metode. For nemheds skyld tager denne funktion det sidste element som omdrejningspunkt. Kontroller derefter hvert element og bytter det før omdrejningspunktet, hvis dets værdi er mindre.

Ved slutningen af ​​partitionen er alle elementer mindre end omdrejningspunktet til venstre for den, og alle elementer større end drejningen er til højre for den. Pivoten er i sin endelige sorterede position, og funktionen returnerer denne position:

privat int-partition (int arr [], int start, int end) {int pivot = arr [end]; int i = (start-1); for (int j = start; j <end; j ++) {if (arr [j] <= pivot) {i ++; int swapTemp = arr [i]; arr [i] = arr [j]; arr [j] = swapTemp; }} int swapTemp = arr [i + 1]; arr [i + 1] = arr [ende]; arr [ende] = swapTemp; returnere i + 1; }

4. Algoritmeanalyse

4.1. Tidskompleksitet

I bedste fald opdeler algoritmen listen i to underlister af samme størrelse. Så den første iteration af det fulde n-størrelse liste behov På). Sortering af de resterende to underlister med n / 2 elementer tager 2 * O (n / 2) hver. Som et resultat har QuickSort-algoritmen kompleksiteten af O (n log n).

I værste fald vil algoritmen kun vælge et element i hver iteration, så O (n) + O (n-1) +… + O (1), som er lig med O (n2).

I gennemsnit har QuickSort det O (n log n) kompleksitet, hvilket gør den velegnet til store datamængder.

4.2. QuickSort vs MergeSort

Lad os diskutere i hvilke tilfælde vi skal vælge QuickSort frem for MergeSort.

Selvom både Quicksort og Mergesort har en gennemsnitlig tidskompleksitet på O (n log n), Quicksort er den foretrukne algoritme, da den har en O (log (n)) rumkompleksitet. Mergesort kræver derimod På) ekstra lagerplads, hvilket gør det ret dyrt for arrays.

Quicksort kræver adgang til forskellige indekser for sine operationer, men denne adgang er ikke direkte mulig i sammenkædede lister, da der ikke er nogen sammenhængende blokke; derfor for at få adgang til et element skal vi gentage gennem hver node fra begyndelsen af ​​den linkede liste. Mergesort er også implementeret uden ekstra plads til LinkedLists.

I sådanne tilfælde foretrækkes generelt faste omkostninger for Quicksort og Mergesort.

5. Konklusion

Quicksort er en elegant sorteringsalgoritme, der er meget nyttig i de fleste tilfælde.

Det er generelt en "in-place" algoritme med den gennemsnitlige tidskompleksitet på O (n log n).

Et andet interessant punkt at nævne er, at Java'er Arrays.sort () metoden bruger Quicksort til at sortere arrays af primitiver. Implementeringen bruger to drejninger og fungerer meget bedre end vores enkle løsning, det er derfor for produktionskode det normalt bedre at bruge biblioteksmetoder.

Som altid kan koden til implementering af denne algoritme findes på vores GitHub-lager.