Quick Sort
Zuletzt aktualisiert
Quicksort ist ein Teile-und-herrsche-Algorithmus, der um ein „Pivot“ herum sortiert. Er wählt ein Pivot-Element und partitioniert dann das Array so, dass alles Kleinere davor und alles Größere danach kommt - wodurch das Pivot in seiner endgültigen sortierten Position fixiert wird. Anschließend rekursiert er über die linke und die rechte Partition. Diese Visualisierung verwendet das Lomuto-Schema mit dem letzten Element als Pivot. Drücke auf Abspielen, um die Partitionierung und die Pivot-Platzierung zu sehen.
Quicksort ist in der Praxis meist die schnellste universelle Sortierung dank guten Cache-Verhaltens und In-place-Partitionierung, mit einem Durchschnitt von O(n log n). Der schlechteste Fall ist O(n²) (z. B. ein bereits sortiertes Array bei schlechter Pivot-Wahl), den gute Pivot-Strategien wie Median-of-Three oder Randomisierung vermeiden.
Zeit- und Speicherkomplexität
| Fall | Komplexität | Anmerkungen |
|---|---|---|
| Bester Fall | O(n log n) | Ausgeglichene Partitionen |
| Durchschnittsfall | O(n log n) | Zufällige Reihenfolge |
| Schlechtester Fall | O(n²) | Durchgängig unausgeglichene Pivots |
| Speicher | O(log n) | Rekursionsstapel (In-place-Partitionierung) |
| Stabil | Nein | Partitionstausche ordnen gleiche Elemente um |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Wähle ein Pivot (hier das letzte Element des Bereichs). |
| 2 | Partitionieren: Verschiebe alle Elemente, die kleiner als das Pivot sind, nach links davon. |
| 3 | Tausche das Pivot an die Grenze - es ist nun in seiner endgültigen Position. |
| 4 | Wende Quicksort rekursiv auf die linke Partition an. |
| 5 | Wende Quicksort rekursiv auf die rechte Partition an. |
Durchgerechnetes Beispiel
Sortieren von [5, 2, 4, 1] mit dem Lomuto-Schema (letztes Element als Pivot):
| Durchlauf | Array | Aktion |
|---|---|---|
| Start | [5, 2, 4, 1] | Partitioniere den gesamten Bereich; das Pivot ist 1 (letztes Element). |
| 1 | [1, 2, 4, 5] | Nichts ist kleiner als 1, also tausche 1 an den Index 0; das Pivot 1 ist nun endgültig. Rekursion rechts auf [2, 4, 5]. |
| 2 | [1, 2, 4, 5] | Partitioniere [2, 4, 5] mit Pivot 5; sowohl 2 als auch 4 sind kleiner, also bleibt 5 am Ende und ist endgültig. Rekursion links auf [2, 4]. |
| 3 | [1, 2, 4, 5] | Partitioniere [2, 4] mit Pivot 4; 2 ist kleiner, also bleibt 4 an Ort und Stelle und ist endgültig. 2 ist ein einzelnes Element und somit bereits sortiert. |
| Fertig | [1, 2, 4, 5] | Jedes Pivot ist an seinem Platz fixiert; das Array ist sortiert. |
Wann Quicksort verwenden
| Verwende es, wenn | Vermeide es, wenn |
|---|---|
| Du eine schnelle, universelle In-Memory-Sortierung mit kleinen konstanten Faktoren brauchst. | Du eine garantierte O(n log n)-Laufzeit im schlechtesten Fall brauchst (nutze Heapsort oder Mergesort). |
Der Speicher knapp ist - die Partitionierung erfolgt in place und benötigt nur O(log n) Stapelspeicher. | Du eine stabile Sortierung brauchst, die die Reihenfolge gleicher Schlüssel bewahrt. |
| Die Daten in zufälliger oder unbekannter Reihenfolge vorliegen und du ein zufälliges oder Median-of-Three-Pivot verwendest. | Die Eingabe bereits sortiert oder fast sortiert ist und das Pivot fest ist, was O(n²) auslöst. |
| Gute Cache-Lokalität wichtig ist, da Quicksort sequenziell auf den Speicher zugreift. | Du eine verkettete Liste sortierst, wo Mergesort den wahlfreien Zugriff vermeidet, auf den Quicksort angewiesen ist. |
Quick Sort-Code
Eine saubere, lauffähige Quick Sort-Implementierung in Python, JavaScript, Java, C++, C, Pseudocode. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Quick Sort-Code in Python
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)Quick Sort-Code in JavaScript
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));Quick Sort-Code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}Quick Sort-Code in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}Quick Sort-Code in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}Quick Sort-Code in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12
13FUNCTION partition(lo : INTEGER, hi : INTEGER) RETURNS INTEGER14 DECLARE pivot : INTEGER15 DECLARE a : INTEGER16 DECLARE b : INTEGER17 DECLARE temp : INTEGER18 pivot ← nums[hi]19 a ← lo - 120 FOR b ← lo TO hi - 121 IF nums[b] <= pivot THEN22 a ← a + 123 temp ← nums[a]24 nums[a] ← nums[b]25 nums[b] ← temp26 ENDIF27 NEXT b28 temp ← nums[a + 1]29 nums[a + 1] ← nums[hi]30 nums[hi] ← temp31 RETURN a + 132ENDFUNCTION33
34PROCEDURE quickSort(lo : INTEGER, hi : INTEGER)35 DECLARE p : INTEGER36 IF lo < hi THEN37 // Place the pivot, then sort each side of it38 p ← partition(lo, hi)39 CALL quickSort(lo, p - 1)40 CALL quickSort(p + 1, hi)41 ENDIF42ENDPROCEDURE43
44CALL quickSort(1, n)45
46FOR i ← 1 TO n47 OUTPUT nums[i]48NEXT iQuick Sort FAQ
Wie ist die Zeitkomplexität von Quicksort?
Quicksort liegt im Durchschnitt bei
O(n log n) und ist im besten Fall O(n log n), verschlechtert sich aber im schlechtesten Fall auf O(n²), wenn die Partitionen durchgängig unausgeglichen sind. Zufällige oder Median-of-Three-Pivots machen den schlechtesten Fall sehr unwahrscheinlich.Ist Quicksort stabil?
Nein. Die übliche In-place-Partitionierung tauscht weit entfernte Elemente, was die relative Reihenfolge gleicher Schlüssel ändern kann. Es gibt stabile Varianten, die jedoch den In-place-Vorteil von Quicksort aufgeben.
Warum ist Quicksort oft schneller als Mergesort?
Quicksort partitioniert in place mit ausgezeichneter Cache-Lokalität und ohne zusätzlichen Puffer, daher sind seine Konstanten klein. Mergesort erreicht dieselbe
O(n log n)-Schranke, zahlt aber für einen O(n)-Puffer und mehr Datenbewegung.Quicksort vs. Mergesort - welches sollte ich verwenden?
Wähle Quicksort für schnelles, In-place-Sortieren von Arrays im Speicher, wo seine kleinen Konstanten meist gewinnen. Wähle Mergesort, wenn du eine stabile Sortierung, einen garantierten
O(n log n)-Worst-Case oder das Sortieren von verketteten Listen oder externen Daten brauchst, die nicht in den RAM passen.Warum wird Quicksort bei einem sortierten Array zu O(n²)?
Bei einem festen Pivot wie dem ersten oder letzten Element sorgt eine bereits sortierte Eingabe dafür, dass jede Partition nur ein Element abspaltet, was
n statt log n Rekursionsebenen erzeugt. Das Pivot zufällig oder per Median-of-Three zu wählen durchbricht dieses Muster und stellt das O(n log n)-Verhalten wieder her.Was ist der Unterschied zwischen dem Lomuto- und dem Hoare-Partitionierungsschema?
Das Lomuto-Schema verwendet einen einzelnen Index, der von links nach rechts läuft, und ist einfacher zu programmieren, weshalb diese Visualisierung es nutzt. Das Hoare-Schema verwendet zwei Zeiger, die nach innen wandern, und führt in der Regel weniger Tausche durch, was es in der Praxis schneller macht, aber es platziert das Pivot während des Partitionierungsschritts nicht an seiner endgültigen Position.
Verwandte Ressourcen
Mehr Visualisierungen
