DseWiki: QuickSort

QuickSort ist ein Sortier-Algorithmus welcher als erstes von C. A. R. Hoare in 1962 beschrieben wurde. Er heißt zu Recht QuickSort, denn er ist im Normalfall wohl der schnellste existierende Sortieralgorithmus. (Implementierung siehe /Implementation)

Funktionsweise von QuickSort

Quicksort an einem Beispiel

Um ein Array zu sortieren, wählt QuickSort zunächst eine spezielle Zahl im Array, die wir Pivot nennen wollen. Wie das Pivot gewählt wird, sehen wir uns später an. Dann werden alle Zahlen, welche kleiner als das Pivot sind, auf die linke Seite des Arrays gebracht, alle Zahlen, welche größer als das Pivot sind, werden auf die rechte Seite des Arrays gebracht. Als Beispiel betrachten wir das Array mit den Zahlen

7 10 8 6 11 4 9 3 1 5 2 12

Der Übersichtlichkeit halber haben wir die Zahlen kleiner als 7, welches wir als Pivotelement wählen, blau markiert. Die Zahlen größer 7 haben wir rot markiert. Dass die 7 gerade am Anfang des Arrays steht, betrachten wir zunächst als Zufall. Als ersten Schritt ändert QuickSort das Array nun folgendermaßen:

3 2 5 6 1 4 7 9 11 8 10 12

Nun sind alle Zahlen, welche kleiner sind als 7, links von ihr. Alle Zahlen welche größer sind als die 7, sind rechts von ihr. Dabei interessiert es uns im Moment gar nicht, in welcher Reihenfolge die Zahlen links und rechts von der 7 stehen. Alles was wir fordern, ist, dass alle blauen Zahlen links von der 7 sind, die roten Zahlen rechts von der 7.

Als nächstes sortieren wir den Teil links von der 7 wieder mit QuickSort. Als Pivot wählen wir die 3. Wieder markieren wir die Zahlen kleiner als drei mit blau, die grösseren Zahlen mit rot. Die Zahl 7 und die grösseren Zahlen betrachten wir im Moment nicht, deshalb markieren wir sie gelb:

3 2 5 6 1 4 7 9 11 8 10 12

QuickSort bringt die blauen und die roten Zahlen wieder in die richtige Ordnung. Man erhält dann das Folgende:

1 2 3 6 5 4 7 9 11 8 10 12

Das wird fortgesetzt bis der linke Teil des Arrays sortiert ist. Das sieht dann wie folgt aus:

1 2 3 4 5 6 7 9 11 8 10 12

Nun wird rechts von der 7 sortiert. Wieder wird ein Pivot gewählt, hier die 9, und die kleineren und grösseren Zahlen auf die jeweils richtige Seite gebracht.

Wir können nun bereits den grundsätzlichen Algorithmus mit PseudoCode beschreiben:

procedure QuickSort(int[] Array, int L, int R) if L < R mitte := partitioniere(Array, L, R) QuickSort(Array, L, mitte-1) QuickSort(Array, mitte+1, R) endif endprocedure

Dabei wählt die Prozedur partitioniere ein Pivot, und bringt die Zahlen, die kleiner sind, auf die linke Seite von dem Pivot und die grösseren Zahlen auf die rechte Seite des Pivots. Sie partioniert das Array. Als Rückgabewert gibt partitioniere die neue Position des Pivots zurück.

Wir müssen uns noch zwei Dinge überlegen:

Wie partitionieren wir ein Array?
Wie wählen wir das Pivot?

Wir wenden uns zunächst der Wahl des Pivot-Elements zu.

Wahl des Pivot-Elements

Die Wahl des Pivotelements ist offensichtlich wichtig. Bei einer QuickSortAnalyse? bemerkt man, dass man am Besten das Element als Pivot wählt, welches am Schluss genau in der Mitte zu liegen kommt. In diesem Fall ist die Laufzeit von Quicksort O(n log(n)). Leider ist dieses Element nicht ganz einfach zu finden. Die schlechteste Wahl des Pivots ist das Element, welches ganz am linken oder ganz am rechten Rand des zu sortierenden Intervals endet. Falls man immer dieses Element wählt so ist die Laufzeit von Quicksort O(n^2), also wesentlich schlechter als O(n log(n)).

Man sollte deshalb nicht immer das linke Element als Pivot wählen, so wie wir das in unseren Beispielen getan haben. Falls nämlich das Array bereits sortiert ist, oder nahezu sortiert ist, führt dies zu dem einem äußerst langsamen "QuickSort".

Als Kompromiss wird oft ein zufälliges Element als Pivot-Element genommen. Eine DetaillierteQuickSortAnalyse? zeigt, dass wir dann erwarten können, dass QuickSort in O(n log(n)) läuft. Noch besser kann es sein, von drei zufällig gewählten Elementen jeweils das mittlere zu nehmen.

In unserem Text fahren wir fort und nehmen das linke Element als Pivot, obwohl das in jeder praktischen Implementation schlecht ist.

Partitionierung

Wir wenden uns jetzt der Frage zu, wie man bei gewählten Pivot das Array partitioniert. Also der Frage: wie kommt man effizient von

  7 10  8  6 11  4  9  3  1  5  2 12

auf

2 5 6 1 4 3 7 9 11 8 10 12

Die effiziente Implementation dieses Schrittes ist übrigens der Grund, weshalb QuickSort instabil sortiert. StabilesSortieren ist fast unmöglich mit QuickSort.

Der Einfachheit halber nehmen wir an, dass das Pivot am linken Rand des Arrays steht. Falls dies nicht so ist, so kann man zuerst das linke Element des Arrays mit dem Pivotelement vertauschen.

Die Partitionierung macht man nun üblicherweise folgendermaßen. Man verwendet zwei Zeiger, einen links und einen rechts auf das Array:

7 10 8 6 11 4 9 3 1 5 2 12 ^ ^ L R

Nun geht man mit dem linken Zeiger soweit nach rechts, bis er auf eine rote Zahl zeigt. Mit dem rechten Zeiger geht man soweit nach links, bis er auf eine blaue Zahl zeigt. Danach sieht die Situation wie folgt aus:

7 10 8 6 11 4 9 3 1 5 2 12 ^ ^ L R

Jetzt vertauscht man die Elemente auf welche die Zeiger zeigen:

7 2 8 6 11 4 9 3 1 5 10 12 ^ ^ L R

Wiederum geht man mit dem linken Zeiger bis zur nächsten roten Zahl, mit dem rechten Zeiger bis zur nächsten blauen Zahl:

7 2 8 6 11 4 9 3 1 5 10 12 ^ ^ L R

Nochmals vertauschen:

7 2 5 6 11 4 9 3 1 8 10 12 ^ ^ L R

Wieder weiterziehen:

7 2 5 6 11 4 9 3 1 8 10 12 ^ ^ L R

Und vertauschen:

7 2 5 6 1 4 9 3 11 8 10 12 ^ ^ L R

Nochmals die Zeiger bewegen:

7 2 5 6 1 4 9 3 11 8 10 12 ^ ^ L R

Und ein letzes Mal vertauschen:

7 2 5 6 1 4 3 9 11 8 10 12 ^ ^ L R

Jetzt ziehen wir nochmals weiter (aufpassen, Reihenfolge!)

7 2 5 6 1 4 3 9 11 8 10 12 ^ LR

Und stoppen hier, weil beide Zeiger auf dasselbe Element zeigen. Nun vertauschen wir noch das Pivotelement mit dem Element, auf welches gezeigt wird, und sind fertig:

3 2 5 6 1 4 7 9 11 8 10 12 ^ LR

In PseudoCode könnte das Ganze so aussehen:

procedure partitioniere(int[] Array, int L, int R) L0 := L // Wählt als PivotElement Array[L0]. Dies ist für praktische // Anwendungen SCHLECHT while L < R if Array[R] > Array[L0] R := R - 1 elseif Array[L] <= Array[L0] L := L + 1 else swap(Array, L, R) endif endwhile swap(Array, L0, R) // vertausche mit dem Pivot endprocedure

Weitere Informationen

/Implementation
/Analyse
/DetaillierteAnalyse?
/InDenTopTen

KategorieAlgorithmus KategorieSortierAlgorithmus KategorieLieblingsSeite