Home > Informatik > Stufe Q1

13. Quicksort

Allgemeines

Der Quicksort ist ein komplexeres Sortierverfahren, das in seiner Geschwindigkeit aber Maßstäbe setzt. Im Prinzip handelt es sich um ein rekursives binäres Verfahren. Die Zahl in der Mitte des Arrays wird als "sortiert" betrachtet, und dann werden alle Zahlen links dieses Medians, die größer sind als der Median, nach rechts "geschaufelt". Alle Zahl rechts des Medians, die kleiner sind als dieser, werden dagegen nach links "geschaufelt". Am Ende des ersten Durchgangs sind alle Zahl links des Medians kleiner als dieser, und alle Zahlen rechts des Medians sind größer als dieser. Danach wird der linke Abschnitt in zwei neue Hälften unterteilt, ebenso der rechte. Dann wiederholt sich das Ganze.

Die Seiten zu den einfachen Sortieralgorithmen finden Sie übrigens in der Folge 8 des EF-Lehrgangs.

PDF-Skript

Vor einigen Jahren habe ich ein umfangreiches PDF-Skript erstellt, das ich allerdings nicht mehr aktualisiere, aus Zeitgründen. Sie können sich die alte Version aber gerne kostenlos herunterladen. Wenn Sie sich nur für den Quicksort-Abschnitt interessieren, können Sie auch diesen downloaden.

Grundkursschüler, die mit den Folgen 11 und 12 schon fertig sein sollten, während alle anderen noch an den Aufgaben arbeiten, können ja gern die Folge 13 durcharbeiten.