Sortieralgorithmen/ Quicksort
Quicksort ist ein bekanntes Verfahren und wird oft genutzt. Mit einer schnellen Ausführzeit ist es ein sehr guter Sortieralgorithmus, welcher auch fast keinen zusätzlichen Speicherplatz benötigt. Daher auch der Name, denn quick kommt aus dem Englischen und steht für schnell. Quicksort gehört zu den nicht stabilen Sortierverfahren. (8)
Quicksort wurde 1960 von C. A.R. Hoare, einem britischen Informatiker, entwickelt und 1962 veröffentlicht. (9) Viele weitere Informatiker haben das Prinzip später noch verbessert.
Quicksort ist ein Sortierverfahren, bei dem beispielsweise aus einer Zahlenreihe zufällig eine Zahl genommen wird. Diese Zahl wird In die „Mitte“ gelegt. Es ist das sogenannte Pivotelement, also der Dreh- und Angelpunkt (abgeleitet von dem französischen Wort pivot). (10)
Das Pivotelement bezeichnet die Aufteilungsgrenze. Ideal wäre dazu ein ausgewähltes Element, welches die Elemente in zwei gleich große Hälften teilt, dieses wäre dann der Best-Case, also der Idealfall. Zwingend ist aber, dass jeder Teil mindestens um ein Element kleiner ist, als die Gesamtliste. Bei dem kleinsten bzw. größten Element käme es zu einem Worst-Case. Vom ausgewählten Pivotelement hängen wesentlich die Laufzeit und auch der Speicherplatz ab.
Alle Elemente werden rekursiv, das heißt links und rechts des Pivotelementes sortiert. Es wird die erste Zahl genommen. Ist diese größer, als die in der Mitte liegende Zahl, wird die Zahl „rechts“ der mittig liegenden Zahl gelegt. Ist sie jedoch kleiner, wird sie links der mittig liegenden Zahl gelegt. So geht es weiter, bis alle Zahlen entweder links, oder rechts der mittig liegenden Zahl sind. Dann wird aus diesen zwei Zahlenreihen jeweils wieder eine Zahl entnommen und in die Mitte gelegt. Das heißt wir haben zwei mittig liegende Zahlen (Mitte links und Mitte rechts). Nun werden aus den zwei alten Zahlenreihen wieder alle Zahlen zu den mittig liegenden Zahlen sortiert. Die Zahlen die früher rechts lagen, werden nun zu der Mitte rechts sortiert und die Zahlen die links lagen, werden nun zu Mitte links sortiert. Dieses Verfahren wiederholt sich nun so lange, bis alle Zahlen sortiert sind.
Dieses Verfahren nennt man auch "Teile und herrsche" - im Englischen "divide and conquer". (11) Das bedeutet man teilt in kleine lösbare Probleme, bis man über diese herrscht. Zuletzt wird das Problem im Ganzen gelöst und beherrscht. Die Ergebnisse aus den kleineren Lösungen, also dem linken und dem rechten Teil werden am Ende aneinandergereiht.
An einem Beispiel aus der Realität möchte ich Quicksort noch einmal bildlich darstellen. Eine Firma verkauft Tannenbäume. Ein Auszubildender namens Frank soll die Bäume (5 Stück) schnellstmöglich sortieren. Also nimmt er einen Baum 1 (2.00 m) und stellt ihn in die Mitte. Dieser wäre unser Pivotelement. Nun nimmt er den nächsten Baum 2 (1.80 m) und stellt diesen, da er kleiner, als die erste Tanne ist, links von ihr auf nun nimmt er die dritte Tanne, Baum 3 (1.90 m), und stellt ihn auch links des ersten Baumes. Zum Schluss hat er noch zwei größere Bäume. Baum 4 (2.20 m) und Baum 5 (2.10 m), die er beide rechts der ersten Tanne stellt. Jetzt schaut Frank sich die erste Teilgruppe (Baum 2 und Baum 3) an und vergleicht diese miteinander. Der dritte Baum ist der Größere, also vertauscht er Baum 3 und Baum 2, so dass jetzt Baum 2 an erster Stelle steht und Baum 3 neben Baum 1. Alles ist richtig sortiert, also kann sich Frank jetzt der rechten Teilreihe zuwenden.
In dieser vergleicht er auch wieder beide Bäume (Baum 4 und Baum 5). Die vierte Tanne ist 2.20 m hoch während der fünfte Baum nur 2.10 m groß ist. Somit ist die vierte die größere Tanne und die Aufstellung stimmt hier. Alles ist fertig. Die Bäume sind ihrer Größe nach sortiert. Die Baumreihe würde demzufolge sein: Baum 2, Baum 3, Baum 1, Baum 5, Baum 4.
Nun kann sich Frank wieder einer anderen Aufgabe zuwenden.
Man kann an diesem Beispiel deutlich sehen, dass die richtige Wahl des Pivotelementes ausschlaggebend für die aufzuwendende Zeit ist.