Algorithmen und Datenstrukturen in C/ Quicksort

Vorstellung

Quicksort ist ein rekursiver Sortieralgorithmus, der die zu sortierende Liste in zwei Teillisten unterteilt und alle Elemente, die kleiner sind als das Pivot-Element, in die linke Teilliste, alle anderen in die rechte Teilliste einsortiert.

Obwohl Quicksort im schlechtesten Fall quadratische Laufzeit hat, ist er in der Praxis einer der schnellsten Sortieralgorithmen.

Implementierung

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void quicksort(int *begin, int *end)
{
    int *ptr;
    int *split;
    if (end - begin < 1)
	return;
    ptr = begin;
    split = begin + 1;
    while (++ptr <= end) {
	if (*ptr < *begin) {
	    swap(ptr, split);
	    ++split;
	}
    }
    swap(begin, split - 1);
    quicksort(begin, split - 1);
    quicksort(split, end);
}

Laufzeit-Komplexität

Die Effizienz von Quicksort ist stark von der Wahl des Pivot-Elements abhängig. In der kanonischen Implementierung verwendet man das erste Element der Liste als Pivot. Dies liefert jedoch im Fall einer bereits sortierten Liste die schlechteste Laufzeit.

Quicksort hat im Mittel eine Laufzeit von O(n*log n), im schlechtesten Fall eine Laufzeit von O(n²).

Andere Methoden, das Pivot-Element zu wählen:

Zufällige Auswahl eines Pivot-Elements
Zufällige Auswahl mehrerer möglicher Pivot-Elemente, der Median der Kandidaten wird dann verwendet
...

Standardbibliothek

Die C-Standardbibliothek bietet eine Implementierung von quicksort an. Diese ist in stdlib.h als qsort() deklariert. Wie alle generischen Implementierungen in C verwendet sie Funktionszeiger. Dies wirkt sich allerdings negativ auf die Laufzeit aus.

<< Heapsort | Inhaltsverzeichnis | Externes Sortieren >>