Quicksort
Teilen und Erobern
Quicksort ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Teilen und Herrschen
Quicksort ist ein Sortierverfahren nach dem Prinzip „Teilen und Herrschen“. Es wählt ein Pivot-Element, partitioniert das Array so, dass kleinere Elemente links und größere rechts stehen, und sortiert anschließend beide Seiten rekursiv.
Die durchschnittliche Laufzeit beträgt O(n log n).
Der Partitionierungsschritt
Die zentrale Idee ist die Partitionierung: Das Array wird um ein Pivot-Element herum so umgeordnet, dass alles links vom Pivot kleiner und alles rechts davon größer ist. Danach befindet sich das Pivot an seiner endgültigen sortierten Position.
Lomuto-Partitionsschema
Das Lomuto-Schema verwendet das letzte Element als Pivot. Es verwaltet einen Index i als Grenze der kleineren Elemente und vertauscht Elemente während des Durchlaufs.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Die rekursive Sortierung
Quicksort ruft die Partitionierung auf und arbeitet anschließend rekursiv auf den beiden Teilarrays links und rechts des Pivots. Der Abbruchfall ist ein Teilarray der Größe 0 oder 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Ein gutes Pivot wählen
Ein ungünstiges Pivot (beispielsweise immer das letzte Element bei einer sortierten Eingabe) führt zu einer Laufzeit von O(n²). Bessere Entscheidungen verteilen die Partitionen gleichmäßiger.
- Median aus drei Elementen
- Zufälliges Pivot
Median aus drei Elementen
Bei der Median-aus-drei-Methode wird der Median des ersten, mittleren und letzten Elements als Pivot gewählt. Dadurch wird das Verhalten im schlechtesten Fall bei bereits sortierten Daten vermieden.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Analyse des schlechtesten Falls
Wenn jede Partition nur ein Element abspaltet, erreicht die Rekursionstiefe n und die Laufzeit beträgt O(n²). Das geschieht bei einem festen Pivot und sortierten oder umgekehrt sortierten Eingaben.
Durch Randomisierung wird der schlechteste Fall äußerst unwahrscheinlich.
Zufälliges Pivot
Wenn vor der Partitionierung ein zufälliges Element an die Pivot-Position getauscht wird, schützt dies vor Eingaben, die gezielt einen schlechten Fall herbeiführen.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}In-place und nicht stabil
Quicksort sortiert in-place und benötigt durchschnittlich nur O(log n) Stapelspeicher. Das Verfahren ist jedoch nicht stabil: Gleiche Elemente können durch die Vertauschungen bei der Partitionierung ihre Reihenfolge ändern.
Optimierung von Endrekursionen
Wenn zuerst auf der kleineren Hälfte rekursiv gearbeitet und die größere Hälfte in einer Schleife verarbeitet wird, wird die Stapeltiefe auf O(log n) begrenzt. Dadurch wird ein Stapelüberlauf bei großen Arrays verhindert.
Zeichenketten sortieren
Dieselbe Struktur kann jeden vergleichbaren Datentyp sortieren. Hier ordnet Quicksort ein Array von Ganzzahlen, aber durch Anpassen des Vergleichs lassen sich auch andere Typen verarbeiten.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Kurzer Test
Testen Sie Ihr Verständnis von Quicksort.
Zusammenfassung
Sie haben Quicksort kennengelernt.
- Partitionieren Sie um ein Pivot und arbeiten Sie anschließend auf jeder Seite rekursiv
- Durchschnittlich O(n log n), im schlechtesten Fall O(n²)
- Ein Median aus drei Elementen oder zufällige Pivots vermeiden den schlechtesten Fall
- In-place, aber nicht stabil
Häufig gestellte Fragen
Ist die Lektion „Quicksort“ kostenlos?
Ja — der vollständige Text von „Quicksort“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Quicksort“?
Teilen und Erobern Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um C Academy zu starten?
Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Quicksort“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?
Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.