Wie funktioniert der Quicksort-Algorithmus (mit Pseudocode)?

Quicksort ist ein effizienter, rekursiver Sortieralgorithmus, der das Prinzip "Teile und herrsche" verwendet. Hier sind die Grundzüge des Quicksort-Algorithmus:

1. **Wähle ein Pivotelement**: Ein Element aus dem Array wird als Pivot ausgewählt. Es gibt verschiedene Strategien, das Pivot zu wählen, z.B. das erste Element, das letzte Element, ein zufälliges Element oder das Median-Element.

2. **Partitioniere das Array**: Ordne die Elemente des Arrays so um, dass alle Elemente, die kleiner als das Pivot sind, vor dem Pivot stehen, und alle Elemente, die größer als das Pivot sind, nach dem Pivot. Das Pivot befindet sich danach an seiner endgültigen Position.

3. **Rekursives Sortieren**: Wende den Quicksort-Algorithmus rekursiv auf die beiden Teilarrays an, die durch das Pivot-Element getrennt wurden.

Hier ist ein Beispiel in Pseudocode:

```pseudocode
function quicksort(array, low, high)
if low < high
// Partitioniere das Array und erhalte den Index des Pivots
pivotIndex = partition(array, low, high)

// Rekursiv auf die Teilarrays anwenden
quicksort(array, low, pivotIndex - 1)
quicksort(array, pivotIndex + 1, high)

function partition(array, low, high)
// Wähle das Pivot (hier das letzte Element)
pivot = array[high]
i = low - 1

for j = low to high - 1
if array[j] < pivot
i = i + 1
swap array[i] with array[j]

// Setze das Pivot an die richtige Position
swap array[i + 1] with array[high]
return i + 1

function swap(a, b)
temp = a
a = b
b = temp
```

**Beispiel:**

Angenommen, das Array ist `[10, 7, 8, 9, 1, 5]`.

1. Wähle das Pivot: `5`
2. Partitioniere das Array:
- Nach der Partitionierung: `[1, 5, 8, 9, 10, 7]`
- Pivot `5` ist an der richtigen Position.
3. Rekursiv auf die Teilarrays anwenden:
- Linkes Teilarray: `[1]` (bereits sortiert)
- Rechtes Teilarray: `[8, 9, 10, 7]`
4. Wiederhole den Prozess für das rechte Teilarray:
- Wähle das Pivot: `7`
- Nach der Partitionierung: `[1, 5, 7, 9, 10, 8]`
- Pivot `7` ist an der richtigen Position.
5. Rekursiv auf die neuen Teilarrays anwenden:
- Linkes Teilarray: `[8]` (bereits sortiert)
- Rechtes Teilarray: `[9, 10]` (bereits sortiert)

Am Ende ist das Array sortiert: `[1, 5, 7, 8, 9, 10]`.

Quicksort hat eine durchschnittliche Zeitkomplexität von \(O(n \log n)\), kann aber im schlechtesten Fall \(O(n^2)\) erreichen, wenn das Pivot-Element ungünstig gewählt wird.