Direkt zum Inhalt

Lexikon der Mathematik: Quicksort

allgemeines Sortierverfahren zum Sortieren von n Elementen.

Die Idee des Verfahrens besteht darin, die zu sortierende Eingabemenge, die als Feld A[p..r] abgespeichert ist, in zwei nichtleere Teilfelder A[p..q] und A[q+1…r] so umzuordnen, daß jedes in A[p..q] abgespeicherte Element kleiner oder gleich jedem in A[q + 1..r] abgespeicherten Element ist. Der Index q wird hierbei im Rahmen des Partitionsschritts berechnet, die beiden Teilfelder A[p..q] und A[q + 1..r] werden rekursiv nach dem gleichen Schema sortiert. Das so entstehende Feld A[p..q] ist nach diesem Schritt fertig sortiert.

Zentraler Bestandteil des Verfahrens ist der Partitionierungsschritt. Hier wird das an der ersten Stelle abgespeicherte Element A[p] als Dreh- und Angelpunkt δ benutzt. Der Partitionierungsschritt teilt das Feld A[p..r] so auf, daß alle Elemente aus A[p..q] kleiner gleich δ und alle Elemente aus A[q + 1..r] größer oder gleich δ sind.

Quicksort benötigt im schlechtesten Fall c1 · n2 Schritte für eine von n unabhängige Konstante c1. Dieser Fall liegt gerade dann vor, wenn alle Elemente der Eingabefolge paarweise verschieden und schon sortiert sind. Sind alle Eingabefolgen gleich wahrscheinlich, so benötigt Quicksort im Mittel weniger als c2 · n · [log2n] Schritte für eine sehr kleine, von n unabhängige Konstante c2. Um dieses Mittel auch bei nicht vorliegender Gleichverteilung zu erreichen, wird der Dreh- und Angelpunkt δ zumeist zufällig aus den in A[p..r] abgespeicherten Elementen gewählt. Man spricht in diesem Fall von randomisiertem Quicksort.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.