streamalism.org

1. Overzicht

In deze tutorial zullen we het QuickSort-algoritme in detail verkennen, waarbij we ons concentreren op de Java-implementatie ervan.

We bespreken ook de voor- en nadelen ervan en analyseren vervolgens de tijdscomplexiteit.

2. QuickSort-algoritme

Quicksort is een sorteeralgoritme dat gebruikmaakt van het verdeel-en-heersprincipe. Het heeft een gemiddelde O (n log n) complexiteit en het is een van de meest gebruikte sorteeralgoritmen, vooral voor grote datavolumes.

Het is belangrijk om te onthouden dat Quicksort geen stabiel algoritme is. Een stabiel sorteeralgoritme is een algoritme waarbij de elementen met dezelfde waarden in dezelfde volgorde in de gesorteerde uitvoer verschijnen als in de invoerlijst.

De invoerlijst is verdeeld in twee sublijsten door een element genaamd pivot; een sublijst met elementen kleiner dan het draaipunt en een andere met elementen groter dan het draaipunt. Dit proces herhaalt zich voor elke sublijst.

Ten slotte worden alle gesorteerde sublijsten samengevoegd om de uiteindelijke uitvoer te vormen.

2.1. Algoritme stappen

1. We kiezen een element uit de lijst, de pivot genaamd. We gebruiken het om de lijst op te splitsen in twee sublijsten.
2. We rangschikken alle elementen rond het draaipunt - degenen met een kleinere waarde worden ervoor geplaatst en alle elementen groter dan het draaipunt erna. Na deze stap staat het draaipunt in zijn definitieve positie. Dit is de belangrijke partitiestap.
3. We passen de bovenstaande stappen recursief toe op beide sublijsten links en rechts van het draaipunt.

Zoals we kunnen zien, quicksort is van nature een recursief algoritme, zoals elke verdeel en heersbenadering.

Laten we een eenvoudig voorbeeld nemen om dit algoritme beter te begrijpen.

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

1. Stel dat we 5 kiezen als draaipunt voor eenvoud
2. We plaatsen eerst alle elementen kleiner dan 5 op de eerste positie van de array: {3, 4, 5, 6, 5, 9}
3. We herhalen het dan voor de linker subarray {3,4}, waarbij we 3 als spil nemen
4. Er zijn niet minder dan 3 elementen
5. We passen quicksort toe op de sub-array rechts van het draaipunt, d.w.z. {4}
6. Deze sub-array bestaat uit slechts één gesorteerd element
7. We gaan door met het rechterdeel van de oorspronkelijke array, {6, 5, 9} totdat we de laatste geordende array hebben

2.2. Het optimale draaipunt kiezen

Het cruciale punt in QuickSort is om het beste draaipunt te kiezen. Het middelste element is natuurlijk het beste, omdat het de lijst in twee gelijke sublijsten zou verdelen.

Maar het vinden van het middelste element uit een ongeordende lijst is moeilijk en tijdrovend, daarom nemen we het eerste element, het laatste element, de mediaan of elk ander willekeurig element als spil.

3. Implementatie in Java

De eerste methode is Snel sorteren() die de te sorteren array, de eerste en de laatste index, als parameters aanneemt. Eerst controleren we de indices en gaan we alleen verder als er nog elementen moeten worden gesorteerd.

We krijgen de index van de gesorteerde spil en gebruiken deze om recursief te bellen partitie () methode met dezelfde parameters als de Snel sorteren() methode, maar met verschillende indices:

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

Laten we doorgaan met de partitie () methode. Voor de eenvoud neemt deze functie het laatste element als draaipunt. Controleer vervolgens elk element en verwisselt het vóór het draaipunt als de waarde kleiner is.

Aan het einde van de verdeling bevinden alle elementen minder dan het draaipunt zich links ervan en alle elementen groter dan het draaipunt bevinden zich rechts ervan. Het draaipunt bevindt zich op de laatste gesorteerde positie en de functie retourneert deze positie:

private int partitie (int arr [], int begin, int end) {int pivot = arr [end]; int i = (begin-1); for (int j = begin; 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 [einde]; arr [end] = swapTemp; retourneer i + 1; }

4. Algoritme-analyse

4.1. Tijdscomplexiteit

In het beste geval verdeelt het algoritme de lijst in twee sublijsten van gelijke grootte. Dus de eerste iteratie van het volledige n-grote lijstbehoeften Aan). De overige twee sublijsten sorteren met n / 2 elementen neemt 2 * O (n / 2) elk. Als gevolg hiervan heeft het QuickSort-algoritme de complexiteit van O (n log n).

In het ergste geval selecteert het algoritme slechts één element in elke iteratie, dus O (n) + O (n-1) +… + O (1), wat gelijk is aan O (n2).

Gemiddeld heeft QuickSort O (n log n) complexiteit, waardoor het geschikt is voor big data-volumes.

4.2. QuickSort versus MergeSort

Laten we bespreken in welke gevallen we QuickSort boven MergeSort moeten kiezen.

Hoewel zowel Quicksort als Mergesort een gemiddelde tijdcomplexiteit hebben van O (n log n)Quicksort is het geprefereerde algoritme, aangezien het een O (logboek (n)) ruimte complexiteit. Mergesort daarentegen vereist Aan) extra opslagruimte, waardoor het vrij duur is voor arrays.

Quicksort vereist toegang tot verschillende indices voor zijn bewerkingen, maar deze toegang is niet rechtstreeks mogelijk in gekoppelde lijsten, aangezien er geen doorlopende blokken zijn; om toegang te krijgen tot een element moeten we daarom elk knooppunt doorlopen vanaf het begin van de gekoppelde lijst. Ook wordt Mergesort geïmplementeerd zonder extra ruimte voor LinkedLists.

In dat geval hebben verhogingen van overhead voor Quicksort en Mergesort over het algemeen de voorkeur.

5. Conclusie

Quicksort is een elegant sorteeralgoritme dat in de meeste gevallen erg handig is.

Het is over het algemeen een 'in-place'-algoritme, met een gemiddelde tijdcomplexiteit van O (n log n).

Een ander interessant punt om te vermelden is dat Java's Arrays.sort () methode gebruikt Quicksort voor het sorteren van arrays van primitieven. De implementatie gebruikt twee pivots en presteert veel beter dan onze eenvoudige oplossing, daarom is het voor productiecode meestal beter om bibliotheekmethoden te gebruiken.

Zoals altijd is de code voor de implementatie van dit algoritme te vinden op onze GitHub-repository.