Quicksort (quick sort) in C und C++
In dieser Lektion implementierst du Quicksort, indem du das Array um ein Pivotelement (pivot) herum aufteilst.
Einführung
Quicksort wählt ein Element als Pivot (pivot) und ordnet das Array so um, dass Elemente, die kleiner als das Pivot sind, links stehen und die übrigen rechts. Dann steht das Pivot bereits an seiner endgültigen Position, und der Algorithmus sortiert die beiden Teile rekursiv weiter.
Wichtige Punkte
- Teste mit leeren Eingaben, einem einzigen Element, doppelten Werten und bereits sortierten Daten.
- Zuerst richtig machen, dann optimieren.
- Bevorzuge in echtem Code die fertigen Funktionen der Standardbibliothek.
Quicksort (quick sort) in C und C++ visualisieren
O(n log n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Codebeispiele in C und C++
#include <stdio.h>
void swap(int *left, int *right) {
int temporary = *left;
*left = *right;
*right = temporary;
}
int partition(int *values, int low, int high) {
int pivot = values[high];
int boundary = low;
for (int scan = low; scan < high; ++scan) {
if (values[scan] < pivot) {
swap(&values[boundary++], &values[scan]);
}
}
swap(&values[boundary], &values[high]);
return boundary;
}
void quick_sort(int *values, int low, int high) {
if (low >= high) return;
int pivot = partition(values, low, high);
quick_sort(values, low, pivot - 1);
quick_sort(values, pivot + 1, high);
}
int main(void) {
int values[] = {9, 4, 7, 3, 10, 5};
quick_sort(values, 0, 5);
for (int index = 0; index < 6; ++index) {
printf("%d ", values[index]);
}
}
3 4 5 7 9 10#include <algorithm>
#include <iostream>
#include <vector>
template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
if (last - first < 2) return;
auto pivot = *(last - 1);
auto middle = std::partition(first, last - 1,
[pivot](int value) { return value < pivot; });
std::iter_swap(middle, last - 1);
quick_sort(first, middle);
quick_sort(middle + 1, last);
}
int main() {
std::vector values{9, 4, 7, 3, 10, 5};
quick_sort(values.begin(), values.end());
for (int value : values) {
std::cout << value << ' ';
}
}
3 4 5 7 9 10C und C++ im Vergleich
Die Funktion partition in C wählt das letzte Element als Pivot und markiert mit der Variablen boundary die Grenze des Bereichs der kleineren Elemente. Zum Schluss wird das Pivot an die Position boundary getauscht. Die C++-Version drückt den Aufteilungsschritt mit std::partition kürzer aus. Die durchschnittliche Komplexität ist O(n log n), bei einem ungünstigen Pivot kann es aber bis zu O(n²) dauern.
Schleifen, Zeiger, Längen und Zwischenpuffer werden ausdrücklich ausgeschrieben.
Iteratoren und Standardalgorithmen trennen die Verarbeitung von der Art, wie die Daten gespeichert sind.
Übungen zur Vertiefung
Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.
- Spiele jeden Vergleich auf Papier durch.
- Teste mit doppelten Werten und mit sehr großen und sehr kleinen Werten.
- Miss die Laufzeit deines Codes und vergleiche sie mit der Standardbibliothek.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
Alle Challenges