Quick Sort: Unheimlich schnell!

Wie funktioniert der Quicksort?

QuickSort ist ein sehr beliebtes Sortierverfahren. „Quick“ ist Englisch und heisst auf Deutsch schnell. Wie der Name sagt, gilt QuickSort tatsächlich als schneller Sortieralgorithmus. Der Sortieralgorithmus QuickSort folgt dem Prinzip „Teilen und Herrschen“, das besagt, dass kleinere Gruppen von Elementen (Personen) besser beherrscht werden können. Die geordneten Gruppen werden dann wieder geteilt und dabei nach der Grösse geordnet. Dies wird solange weitergeführt, bis eine Gruppe nur noch ein Element umfasst. Dann steht es automatisch an der richtigen Stelle. In unserem Beispiel sind es Studentinnen und Studenten, die das Prinzip vorführen.

QuickSort funktioniert so:

1. Zuerst wird die unsortierte Liste der Personen halbiert, indem eine Person aus der Mitte gewählt wird. Dazu werden die Personen gezählt und durch zwei geteilt. Nun sollen alle Elemente, die kleiner als diese mittlere Person sind, links davon stehen, die grösseren rechts davon.
2. Nun wird von ganz links ausgehend die Person gesucht, die grösser oder gleich der mittleren Person ist und ganz rechts jeweils die Person gesucht, die kleiner als die mittlere ist und damit auf der falschen Seite der mittleren Person steht. Sind zwei Personen gefunden, die diese Bedingung erfüllen, so werden diese zwei vertauscht.
3. Dieser Vorgang wird solange wiederholt, bis man von beiden Seiten bei der mittleren Person angelangt ist. Nun sollten alle kleineren Personen links der mittleren Person stehen, auf der rechten Seite alle grösseren Personen. Das mittlere Element ist damit an der endgültigen Position der Reihe angelangt und muss nicht mehr verschoben werden.
4. Anschliessend werden die beiden Gruppen links und rechts der mittleren Person noch je einmal halbiert. Nun wird wieder dasselbe Verfahren angewandt. Grössere Personen der Teilgruppe werden mit kleineren Personen vertauscht, sodass die grösseren Personen rechts der mittleren Person der Teilgruppe stehen, die kleineren Personen links davon.
5. Dieser QuickSort-Algorithmus wird so oft wiederholt, bis die Gruppen nur noch ein Element enthalten. Damit sind alle entsprechenden Personen an der richtigen Stelle positioniert.

Andere Beispiele

Den Sortieralgorithmus QuickSort künnen Sie hier ansehen:
http://www.sorting-algorithms.com/quick-sort

Spannend ist ein grafischer Vergleich, wenn Sie einen anderen Sortieralgorithmus wählen, denn Sie bereits kennengelernt haben.

Weiter mit: Das Rätsel lösen

< Zurück Weiter >