Java Entwickler Experte
Quick sort – schnelles Sortieren mit Pivot in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Heute werden wir uns die schnelle Sortierung mit Pivot ansehen (quick sort). Bislang haben wir die folgenden Sortieralgorithmen behandelt:
In diesem Artikel erfährst du:
- Sortieralgorithmen: eine Einführung in das Sortieren von Daten,
- Bubble sort – Blasen-Sortierung,
- Comb sort – Kamm-Sortierung,
- Big O Notation: Analyse der Komplexität von Algorithmen,
- Auswahlsortierung – Sortieren nach Auswahl,
- Einfügungssortierung – Sortieren nach Einfügung,
- Counting sort – Sortieren durch Zählen,
- Heap sort – Heap Sortierung
- Merge sort – Sortieren durch Aufteilen und Zusammenführen.
Quick sort Algorithmus
Quick sort ist ein sehr beliebter, vielseitiger und effizienter Datensortieralgorithmus, der zwischen 1959 und 1961 von dem britischen Informatiker Tony Hoare entwickelt wurde. Wie Merge sort verwendet er die Technik„Teile und herrsche„, deren Grundidee darin besteht, ein komplexes Problem in kleinere Teile zu zerlegen und diese Teile separat zu lösen. Quick sort ist interessant, weil es versucht, ein Array-Element zuerst an der richtigen Stelle zu platzieren – ein sogenannter Pivot, der die besondere Eigenschaft hat, dass alle Array-Elemente, die kleiner als er sind, im linken Teil und alle Array-Elemente, die größer als er sind, im rechten Teil liegen. Die Elemente in beiden Teilen sind jedoch noch nicht korrekt sortiert. Da sich der Pivot jedoch an der richtigen Stelle im sortierten Ausgabevektor befindet, kann er als Ort dienen, um das Array in zwei Teile – Partitionen – zu unterteilen. Die beiden Teile werden dann als separate Arrays betrachtet, die mit neuen Pivots weiter aufgeteilt werden können, bis die Teile nur noch ein Element enthalten. Das Ergebnis der Sortierung ist eine Sammlung der Sortierergebnisse der einzelnen Partitionen. Im Allgemeinen ist Quicksort schneller als Mergesort und Heapsort, vor allem, wenn wir eine zufällige Anordnung von Elementen in einem großen Datensatz haben, der sortiert werden muss. Es sollte jedoch betont werden, dass die Leistung des Algorithmus stark von der richtigen Wahl des Pivots abhängt. Eine unglückliche Wahl des Pivots kann zu einer Zeitkomplexität führen, die höher ist als die der beiden oben genannten Algorithmen.ok
Quick sort – das Prinzip des Algorithmus
Wie wir bereits erwähnt haben, besteht das Ziel des Algorithmus darin, für einen gegebenen Eingabevektor ein Element – den Pivot – auszuwählen, das den Vektor optimal in zwei annähernd große Partitionen unterteilt, wobei alle Elemente links kleiner und rechts größer als der Pivot sind. Der ungünstigste Fall tritt ein, wenn wir einen Pivot wählen, bei dem (fast) alle Elemente links vom Pivot oder rechts davon liegen. Daher gibt es mehrere Methoden, um einen Pivot auszuwählen. Der schnelle Sortieralgorithmus besteht aus den folgenden Schritten:
- Auswahl des Pivotelements,
- das Feld neu anordnen,
- das Feld in Partitionen zu unterteilen.
Quick sort – Auswahl des Pivotelements
Es gibt viele Möglichkeiten, das Pivot-Element auszuwählen. Zu den einfachsten gehören die Auswahl des ersten Elements, die Auswahl des letzten Elements, die Auswahl eines zufälligen Elements, die Auswahl des mittleren Elements usw. Es gibt auch kompliziertere Versionen der Pivot-Auswahl, bei denen wir zum Beispiel drei Elemente zufällig auswählen und den Median als Pivot verwenden.
Quick sort – Neuordnung der Felder
Angenommen, wir haben das letzte Element des Arrays als Drehpunkt gewählt. Wir vergleichen nach und nach die Elemente von Anfang an mit dem Drehpunkt. Wenn das aktuelle Array-Element größer als der Drehpunkt ist, gehen wir zum nächsten Element über, wenn das Element kleiner ist, ersetzen wir es durch eines der vorherigen größeren Elemente. Beim Traversieren benötigen wir zwei Indizes. Der erste Index bestimmt das Element, das gerade mit dem Pivot verglichen wird, der zweite Index bestimmt, wo die Elemente enden, die kleiner als der Pivot sind. Sobald der erste Index den Drehpunkt erreicht, ersetzen wir den Drehpunkt durch das erste Element, das größer als der Drehpunkt ist (die aktuelle Position des zweiten Index). Anhand eines Beispiels in Java werden wir nun besser verstehen, wie man mit diesen Indizes arbeitet.
Quick sort – Unterteilung des Feldes in Partitionen
Der Drehpunkt befindet sich nach der Neuanordnung des Arrays an der richtigen Position und wird als klassifiziertes Element betrachtet. Außerdem wird das ursprüngliche Array in zwei Partitionen aufgeteilt, die wir rekursiv als zwei separate Arrays behandeln, die sortiert werden müssen. Die Schritte 1 bis 3 werden der Reihe nach wiederholt. Die Rekursion endet, wenn nur noch ein einziges Element im Array übrig ist. Das Ergebnis der Sortierung stellt dann die einzelnen Elemente aus allen Partitionen dar.
Quick sort Animation, Visualisierung, gif
Die Quick sort Animation sieht so aus:
Quelle: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Eine Animation des Algorithmus findest du z.B. auf Toptal. Es gibt 8 Arten von Algorithmen, du kannst die Animation auch rückwärts abspielen. Auf dieser Seite kannst du die Schritte des Algorithmus durchlaufen, so dass du den Zeitverbrauch des Algorithmus überprüfen kannst.
Vorteile des Quick Sort Algorithmus
- Effizient für große Zufallsdatensätze,
- während der Sortierung werden keine Daten kopiert (In-place-Sortierung),
- kann parallelisiert werden und so die Rechenlast auf mehrere Prozessoren verteilen.
Nachteile des Quick Sort Algorithmus
- Sie ist nicht stabil,
- Empfindlich gegenüber der Wahl des geeigneten Pivots,
- aufgrund des mit rekursiven Aufrufen und der Partitionsverwaltung verbundenen Overheads ungeeignet für kleine Datensätze.
Quicksort – Zeitkomplexität
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Quick sort | Vertrieb | O(n²) | O(n log n) | O(n log n) | O(log n) | Nein |
Quick Sort – Implementierung, Java-Code
Jetzt schauen wir uns die Implementierung des Quicksort-Algorithmus in Java an.
QuickSort.java
package sorting;
public class QuickSort {
public void sort(int[] data, int low, int high)
{
if (low >= high)
return;
// Pivot index (pi)
int pi = partition(data, low, high);
// Sort both parts of array recursively
sort(data, low, pi - 1);
sort(data, pi + 1, high);
}
private int partition(int[] data, int low, int high) {
// Selection of pivot (last element)
int pivot = data[high];
// Index of last element smaller than pivot
int i = (low - 1);
// Compare each element with pivot
for (int j = low; j < high; j++) {
if (data[j] <= pivot) {
// Swap the smaller element with greater placed on (i+1)
int temp = data[++i];
data[i] = data[j];
data[j] = temp;
}
}
// Swap of pivot
int temp = data[++i];
data[i] = data[high];
data[high] = temp;
// Print some algo information
System.out.println("Pivot selected: " + data[i]);
printArray(data, low, i - 1);
System.out.print("(" + data[i] + ") ");
printArray(data, i + 1, high);
System.out.println();
// Returns the pivot index
return i;
}
// Function to print an array
public void printArray(int[] data)
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
public void printArray(int[] data, int low, int high)
{
for (int i = low; i <= high; i++)
System.out.print(data[i] + " ");
}
}
Main.java
import sorting.QuickSort;
public class Main {
public static void main(String[] args) {
int[] dataToSort = { 9, 1, 8, 2, 7, 3, 5, 6, 4 };
QuickSort quickSort = new QuickSort();
System.out.print("Input: ");
quickSort.printArray(dataToSort);
System.out.println();
quickSort.sort(dataToSort, 0, dataToSort.length - 1);
System.out.print("Sorted: ");
quickSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Lade den Java QuickSort Code hier herunter.
Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
