Quicksort

Gebrauch

Der Quicksort wird gebraucht, um einen Array zu sortieren.

Der Quicksort kann sehr effizient sein, er kann jedoch im schlechtesten Fall genauso ineffizient wie die einfacheren Sortieralgorithmen sein.

Spezifikationen

Beim Quicksort werden im schlechtesten Fall, der aber nur sehr selten vorkommt O(n²) Vergleiche durchgeführt. Die best-case Performance besteht aus O(n * log(n)) Vergleichen. Seine Durchschnittsperformance beträgt O(n * log(n)) Vergleiche.

Der Algorithmus funktioniert als In-place-Algorithmus, da er nur Elemente innerhalb einer Liste vertauscht. Jedoch braucht er für jede Rekursionsebene neuen Speicherplatz und hat damit eine durchschnittliche Space-complexity von O(log(n)) und im schlechtesten Fall eine Space-complexity von O(n).

Funktionsweise

Der Quicksort Algorithmus arbeitet nach dem Teile-und-herrsche-Verfahren.

Das Grundprinzip vom Teile-und-herrsche-Verfahren ist, dass ein Problem, welches sehr schwierig erscheint, so lange in einfachere Teilprobleme zerlegt wird, bis diese beherrschbar, also gelöst sind. Dieses Verfahren kann von einer rekursiven Funktion, also einer Funktion, die sich selber aufruft, durchgeführt werden. Die Lösung des letzten Teilproblems ist dabei auch die Lösung des Gesamtproblems.
Der Quicksort führt dieses Teile-und-herrsche-Verfahren aus, indem er einen unsortierten Array, also das Problem in zwei unsortierte Teilarrays unterteilt. Dies macht er indem er ein beliebiges Element als das sogenannte Pivot-Element definiert. Das Pivot-Element kann am Ende des Arrays stehen, wie beispielsweise im Beispielcode, kann aber auch in der Mitte oder zufällig an einem beliebigen Index innerhalb des zu sortierenden Teilarrays gewählt werden. Der Algorithmus vertauscht die Elemente des Arrays nun so, dass zwei neue Teilarrays entstehen, einer mit Elementen, die alle kleiner oder gleich wie gross das gewählte Pivot-Element sind und der andere mit Elementen, die alle grösser oder gleich dem Pivot-Element sind. Dies kann dadurch gemacht werden, indem für jedes Element getestet wird, ob es kleiner als das Pivot-Element ist oder nicht. Ist es kleiner, dann wird es mit dem ersten Element getauscht, das diese Bedingung nicht erfüllt hat und somit grösser oder gleich dem Pivot-Element sein muss. Wurde der Array in die zwei Teilarrays unterteilt wird das Pivot-Element dazwischengesetzt und befindet sich somit an seiner endgültigen Position. Dieses Verfahren wird nun durch Rekursion auf jeden Teilarray angewandt, bis alle Teilarrays aus lediglich noch einem Element bestehen. Ist dies der Fall ist der Array sortiert.

Beispielcode

Dies ist ein in Python geschriebener Beispielcode:

# arr ist der Array, welcher zu sortieren ist, low der Index des ersten Elements und high der Index des letzten Elements def quickSort(arr, low, high): # Abbruchbedingung, wenn der Array fertig sortiert ist, damit die Funktion nicht unendlich lange läuft if low < high: # Der Index des Elementes auf dem unsortierten linken Teil des Arrays low_index = low # Element, mit dem verglichen wird hat den höchsten Index im Teilarray pivot = arr[high] # Es wird von low bis (und ohne) dem Pivot Element jedes Element mit dem Pivot-Element verglichen for high_index in range(low, high, 1): # Falls der untersuchte Wert kleiner als das Pivot-Element ist if arr[high_index] < pivot: # Die beiden Werte werden miteinander getauscht arr[low_index], arr[high_index] = arr[high_index], arr[low_index] # Low_index wird erhöht, da dieses Element nun kleiner ist als das Pivot Element low_index += 1 # Das Pivot-Element wird dorthin gesetzt wo rechts alle grösser und links alle kleiner sind arr[low_index], arr[high] = arr[high], arr[low_index] # Die Funktion wird mit dem teilsortierten Array erneut aufgerufen und der rechte Teil wird sortiert quickSort(arr, low_index + 1, high) # Die Funktion wird mit dem teilsortierten Array erneut aufgerufen und der linke Teil wird sortiert quickSort(arr, low, low_index - 1) # Der sortierte Array wird zurückgegeben return arr

Dies ist ein in Java geschriebener Beispielcode:

Es können selbstverständlich auch andere Datentypen gebraucht werden.

// arr ist der Array, welcher zu sortieren ist. Die Funktion gibt den sortierten Array zurück public static int quicksort(int[] arr, int low, int high) { // Abbruchbedingung, wenn der Array fertig sortiert ist, damit die Funktion nicht unendlich lange läuft if (low < high) { // Der Index des Elementes auf dem unsortierten linken Teil des Arrays int low_index = low; // Das Pivot-Element des Teilarrays wird an dessen Ende gewählt int pivot = arr[high]; // Es wird von low bis zu dem Pivot-Element jedes Element mit dem Pivot-Element verglichen for (int high_index = low; high_index < high; high_index++) { // Falls der untersuchte Wert kleiner als das Pivot-Element ist if (arr[high_index] < pivot) { // Die beiden Werte werden miteinander getauscht int temp = arr[high_index]; arr[high_index] = arr[low_index] ; arr[low_index] = temp; // Low_index wird erhöht, da dieses Element nun kleiner als das Pivot-Element ist low_index++; } } // Das Pivot-Element wird an die Position gebracht, an der links alle kleiner und rechts alle anderen Elemente grösser sind int temp = arr[low_index]; arr[low_index] = arr[high]; arr[high] = temp; // Die Funktion wird mit dem teilsortierten Array erneut aufgerufen und der rechte Teil wird sortiert quickSort(arr, low_index + 1, high); // Die Funktion wird mit dem teilsortierten Array erneut aufgerufen und der linke Teil wird sortiert quickSort(arr, low, low_index - 1 } // Der sortierte Array wird zurückgegeben return arr; }

Animiertes Beispiel

Drücke Start, um die Animation zu starten. Ändere die Position des Sliders, um die Geschwindigkeit der Animation zu verändern.