Video: Quicksort Algorithmus / Quick Sort Sortierverfahren mit Beispiel (deutsch) 2024
Hier erfahren Sie, wie eine der am häufigsten verwendeten Sortiertechniken in Java funktioniert. Diese Technik heißt Quicksort, und ist eine sehr geniale Rekursion.
Für die meisten von uns herauszufinden, wie Sortieralgorithmen wie Quicksort nur eine intellektuelle Übung sind. In der Java API ist bereits eine Sortierung integriert.
Die Quicksort-Technik sortiert ein Array von Werten mithilfe von Rekursion. Seine grundlegenden Schritte sind somit:
-
Wählen Sie einen beliebigen Wert aus, der innerhalb des Wertebereichs im Array liegt.
Dieser Wert ist der Drehpunkt . Die häufigste Methode zur Auswahl des Drehpunkts besteht darin, einfach den ersten Wert im Array auszuwählen. Die Leute haben einen Doktortitel geschrieben, um zu erfahren, wie man einen Drehpunkt wählt, der zu einer schnelleren Sortierung führt. Bleiben Sie bei der Verwendung des ersten Elements im Array.
-
Ordnen Sie die Werte im Array neu an, sodass alle Werte, die kleiner als der Drehpunkt sind, auf der linken Seite des Arrays liegen und alle Werte, die größer oder gleich dem Drehpunkt sind, auf der rechten Seite des Arrays. Array.
Der Pivot-Wert gibt die Grenze zwischen der linken Seite und der rechten Seite des Arrays an. Es wird wahrscheinlich kein Totpunkt sein, aber das spielt keine Rolle. Dieser Schritt wird als Partitionierung bezeichnet, und die linke und rechte Seite der Arrays sind Partitionen.
-
Behandeln Sie nun jeden der beiden Abschnitte des Arrays als ein separates Array und beginnen Sie mit Schritt 1 für diesen Abschnitt.
Das ist der rekursive Teil des Algorithmus.
Der schwierigste Teil des Quicksort-Algorithmus ist der Partitionierungsschritt, der die Partition so umordnen muss, dass alle Werte, die kleiner als der Drehpunkt sind, auf der linken Seite liegen und alle Elemente, die größer als der Drehpunkt sind Punkt sind auf der rechten Seite. Nehmen wir an, das Array hat diese zehn Werte:
38 17 58 22 69 31 88 28 86 12
Hier ist der Drehpunkt 38, und die Aufgabe des Partitionierungsschritts besteht darin, das Array auf etwas wie das folgende zu verschieben: < 17 12 22 28 31 38 88 69 86 58
Beachten Sie, dass die Werte immer noch nicht in Ordnung sind. Das Array wurde jedoch um den Wert 38 herum geteilt: Alle Werte, die kleiner als 38 sind, befinden sich links von 38, und alle Werte, die größer als 38 sind, befinden sich rechts von 38.
Jetzt können Sie die Array in zwei Partitionen mit dem Wert 38 und wiederholen Sie den Prozess für jede Seite. Der Pivot-Wert selbst geht mit der linken Partition, also ist die linke Partition dies:
17 12 22 28 31 38
Dieses Mal wählt der Partitionierungsschritt 17 als Pivot-Punkt und ordnet die Elemente wie folgt neu an: > 12 17 22 28 31 38
Wie Sie sehen, ist dieser Teil des Arrays jetzt sortiert.Unglücklicherweise erkennt Quicksort dies an diesem Punkt nicht, so dass es ein paar weitere Rekursionen braucht, um sicher zu gehen. Aber das ist der grundlegende Prozess.
