Implementierung des Quicksort-Algorithmus in Java

1. Übersicht

In diesem Tutorial werden wir den QuickSort-Algorithmus im Detail untersuchen und uns auf seine Java-Implementierung konzentrieren.

Wir werden auch die Vor- und Nachteile diskutieren und dann die zeitliche Komplexität analysieren.

2. QuickSort-Algorithmus

Quicksort ist ein Sortieralgorithmus, der das Divide-and-Conquer-Prinzip nutzt. Es hat eine durchschnittliche O (n log n) -Komplexität und ist einer der am häufigsten verwendeten Sortieralgorithmen, insbesondere für große Datenmengen.

Es ist wichtig zu bedenken, dass Quicksort kein stabiler Algorithmus ist. Ein stabiler Sortieralgorithmus ist ein Algorithmus, bei dem die Elemente mit denselben Werten in der sortierten Ausgabe in derselben Reihenfolge angezeigt werden wie in der Eingabeliste.

Die Eingabeliste wird durch ein Element namens Pivot in zwei Unterlisten unterteilt. Eine Unterliste mit Elementen, die kleiner als der Drehpunkt sind, und eine andere mit Elementen, die größer als der Drehpunkt sind. Dieser Vorgang wird für jede Unterliste wiederholt.

Schließlich werden alle sortierten Unterlisten zusammengeführt, um die endgültige Ausgabe zu bilden.

2.1. Algorithmusschritte

  1. Wir wählen ein Element aus der Liste aus, das als Pivot bezeichnet wird. Wir werden es verwenden, um die Liste in zwei Unterlisten zu unterteilen.
  2. Wir ordnen alle Elemente um den Pivot herum neu an - diejenigen mit kleinerem Wert werden davor platziert und alle Elemente, die größer als der Pivot sind, danach. Nach diesem Schritt befindet sich der Drehpunkt in seiner endgültigen Position. Dies ist der wichtige Partitionsschritt.
  3. Wir wenden die obigen Schritte rekursiv auf beide Unterlisten links und rechts vom Pivot an.

Wie wir sehen können, ist Quicksort natürlich ein rekursiver Algorithmus, wie jeder Divide and Conquer-Ansatz.

Nehmen wir ein einfaches Beispiel, um diesen Algorithmus besser zu verstehen.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Nehmen wir an, wir wählen der Einfachheit halber 5 als Drehpunkt
  2. Wir setzen zuerst alle Elemente unter 5 an die erste Position des Arrays: {3, 4, 5, 6, 5, 9}
  3. Wir wiederholen es dann für das linke Unterarray {3,4} und nehmen 3 als Drehpunkt
  4. Es gibt keine Elemente unter 3
  5. Wir wenden Quicksort auf das Sub-Array rechts vom Pivot an, dh {4}
  6. Dieses Unterarray besteht nur aus einem sortierten Element
  7. Wir fahren mit dem rechten Teil des ursprünglichen Arrays fort, {6, 5, 9}, bis wir das endgültig geordnete Array erhalten

2.2. Auswahl des optimalen Pivots

Der entscheidende Punkt in QuickSort ist die Auswahl des besten Pivots. Das mittlere Element ist natürlich das beste, da es die Liste in zwei gleiche Unterlisten aufteilen würde.

Das mittlere Element aus einer ungeordneten Liste zu finden ist jedoch schwierig und zeitaufwändig. Deshalb nehmen wir das erste Element, das letzte Element, den Median oder ein anderes zufälliges Element als Dreh- und Angelpunkt.

3. Implementierung in Java

Die erste Methode ist quickSort (), die als Parameter das zu sortierende Array, den ersten und den letzten Index verwendet. Zuerst überprüfen wir die Indizes und fahren nur fort, wenn noch Elemente zu sortieren sind.

Wir erhalten den Index des sortierten Pivots und rufen damit rekursiv die partition () -Methode mit denselben Parametern wie die quickSort () -Methode auf, jedoch mit unterschiedlichen Indizes:

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

Fahren wir mit der partition () -Methode fort. Der Einfachheit halber nimmt diese Funktion das letzte Element als Drehpunkt. Überprüft dann jedes Element und tauscht es vor dem Pivot aus, wenn sein Wert kleiner ist.

Am Ende der Partitionierung befinden sich alle Elemente, die kleiner als der Drehpunkt sind, links davon und alle Elemente, die größer als der Drehpunkt sind, rechts davon. Der Drehpunkt befindet sich an seiner endgültigen sortierten Position und die Funktion gibt diese Position zurück:

private int partition(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[end]; arr[end] = swapTemp; return i+1; }

4. Algorithmusanalyse

4.1. Zeitliche Komplexität

Im besten Fall teilt der Algorithmus die Liste in zwei gleich große Unterlisten. Die erste Iteration der vollständigen Liste mit n Größen benötigt also O (n) . Das Sortieren der verbleibenden zwei Unterlisten mit n / 2 Elementen erfordert jeweils 2 * O (n / 2) . Infolgedessen hat der QuickSort-Algorithmus die Komplexität von O (n log n) .

Im schlimmsten Fall wählt der Algorithmus nur ein Element in jeder Iteration aus, also O (n) + O (n-1) +… + O (1) , was gleich O (n2) ist .

Im Durchschnitt weist QuickSort eine Komplexität von O (n log n) auf , sodass es für große Datenmengen geeignet ist.

4.2. QuickSort vs MergeSort

Lassen Sie uns diskutieren, in welchen Fällen wir QuickSort anstelle von MergeSort wählen sollten.

Obwohl sowohl Quicksort als auch Mergesort eine durchschnittliche Zeitkomplexität von O (n log n) aufweisen , ist Quicksort der bevorzugte Algorithmus, da es eine O (log (n)) - Raumkomplexität aufweist. Mergesort erfordert andererseits O (n) zusätzlichen Speicher, was es für Arrays ziemlich teuer macht.

Quicksort muss für seine Operationen auf verschiedene Indizes zugreifen, dieser Zugriff ist jedoch in verknüpften Listen nicht direkt möglich, da keine fortlaufenden Blöcke vorhanden sind. Um auf ein Element zuzugreifen, müssen wir daher vom Anfang der verknüpften Liste durch jeden Knoten iterieren. Außerdem wird Mergesort ohne zusätzlichen Speicherplatz für LinkedLists implementiert.

In diesem Fall wird im Allgemeinen eine Erhöhung des Overheads für Quicksort und Mergesort bevorzugt.

5. Schlussfolgerung

Quicksort ist ein eleganter Sortieralgorithmus, der in den meisten Fällen sehr nützlich ist.

Es handelt sich im Allgemeinen um einen "In-Place" -Algorithmus mit der durchschnittlichen Zeitkomplexität von O (n log n).

Ein weiterer interessanter Punkt ist, dass die Java- Methode Arrays.sort () Quicksort zum Sortieren von Arrays von Grundelementen verwendet. Die Implementierung verwendet zwei Pivots und bietet eine viel bessere Leistung als unsere einfache Lösung. Deshalb ist es für Produktionscode normalerweise besser, Bibliotheksmethoden zu verwenden.

Wie immer finden Sie den Code für die Implementierung dieses Algorithmus in unserem GitHub-Repository.