In Kapitel 5 haben Sie eine einfache Sortiermethode namens
gesehen Blasensortierung. Damals wurde erwähnt, dass es
gibt deutlich bessere Bewertungen. Hier entwickeln Sie eine Version einer der besten: Schnellsortierung (Quicksort).
Schnelle Klassifizierung, erfunden und benannt von C.A.R. Hoare ist der derzeit beste Allzweck-Klassifizierungsalgorithmus. Ich konnte es in Kapitel 5 nicht zeigen, da die beste Implementierung der schnellen Sortierung auf Rekursion basiert. Die Version, die wir entwickeln werden, sortiert ein Array von Zeichen, aber die Logik kann angepasst werden, um jede Art von Objekt zu sortieren.
Die schnelle Sortierung basiert auf der Idee von Partitionen. Das allgemeine Verfahren besteht darin, einen Wert auszuwählen (Vergleichen genannt) und das Array dann in zwei Abschnitte zu unterteilen. Alle Elemente, die größer oder gleich dem Partitionswert sind, werden auf einer Seite und kleinere auf der anderen Seite eingefügt. Dieser Vorgang wird für jeden verbleibenden Abschnitt wiederholt, bis das Array sortiert ist. Wenn beispielsweise das Array „fedacb“ gegeben ist und der Wert „d“ als Vergleich verwendet wird, würde der erste Durchgang der Schnellsortierung das Array wie unten gezeigt neu anordnen:

Initial f e d a c b
Passage 1 b c a d e f

Dieser Vorgang wird dann für jeden Abschnitt wiederholt – also bca und def. Wie Sie sehen, ist der Prozess im Wesentlichen rekursiver Natur, und tatsächlich ist die sauberste Implementierung der Schnellsortierung rekursiv.
Sie können den Vergleichswert auf zwei Arten auswählen. Sie können es zufällig auswählen oder den Durchschnitt einer kleinen Menge von Werten aus dem Array ermitteln. Um eine optimale Klassifizierung zu erhalten, müssen Sie einen Wert auswählen, der genau in der Mitte des Wertebereichs liegt. Bei den meisten Datensätzen ist dies jedoch nicht einfach. Der schlimmste Fall ist, wenn der ausgewählte Wert an einem Ende liegt. Trotzdem wird die Schnellsortierung korrekt ausgeführt.
Die Version der Schnellsortierung, die wir entwickeln werden, wählt das mittlere Element des Arrays als Vergleich aus.

Siehe QSDemo.java.

Schnellsortierung:

• Einer der effizientesten und am weitesten verbreiteten Klassifizierungsalgorithmen.
• Erfunden von C.A.R. Hoare.
• Basierend auf dem Konzept der Partitionen, bei dem das Array in Abschnitte unterteilt ist, die rekursiv sortiert werden.
• Effizienter als Blasensortierung und andere einfache Methoden.

Betrieb:

• Vergleichswert (Pivot):
• Ein Wert wird als Referenz (Pivot) ausgewählt und das Array wird um diesen Wert herum organisiert.
• Elemente, die kleiner als der Drehpunkt sind, gehen auf eine Seite und größere auf die andere.
• Der Vorgang wird für jeden Abschnitt rekursiv wiederholt, bis das Array vollständig sortiert ist.

Quicksort

QSDemo