Sortierung
Sortieren ist der Vorgang, eine Datenmenge in einer bestimmten Reihenfolge neu anzuordnen, und ist eines der fundamentalsten und am intensivsten untersuchten algorithmischen Probleme der Datenverarbeitung.
Familie der Sortieralgorithmen
Einfache Sortierverfahren (O(n²))
Bubblesort, Selectionsort und Insertionsort sind einfach zu implementieren und eignen sich für kleine Datenmengen oder zum Vermitteln von Verständnis.
Fortgeschrittene Sortierverfahren (O(n log n))
Quicksort, Mergesort und Heapsort sind die in der Praxis am weitesten verbreiteten. Shellsort ist eine Verbesserung von Insertionsort.
Beispiele
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Bubblesort — O(n²), stabil
Jede Runde lässt das größte Element ans Ende "blubbern" */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* Optimierung: vorzeitiger Abbruch */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break; /* Bereits sortiert, vorzeitig beenden */
}
}
/* Quicksort-Partitionsfunktion — durchschnittlich O(n log n), instabil
Wähle Pivot; Elemente, die kleiner als das Pivot sind, kommen nach links, größere nach rechts */
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* Das letzte Element als Pivot wählen */
int i = low - 1; /* i zeigt auf das Ende des Bereichs, der kleiner als das Pivot ist */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* Pivot an seine korrekte Position setzen */
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); /* Partitionsindex */
quickSort(arr, low, pi - 1); /* Linke Hälfte rekursiv sortieren */
quickSort(arr, pi + 1, high); /* Rechte Hälfte rekursiv sortieren */
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = 7;
bubbleSort(arr1, n1);
printf("Bubblesort: "); printArray(arr1, n1);
/* Ausgabe: 11 12 22 25 34 64 90 */
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr2, 0, 6);
printf("Quicksort: "); printArray(arr2, 7);
/* Ausgabe: 11 12 22 25 34 64 90 */
return 0;
}
Veranschaulichung des Divide-and-Conquer-Konzepts
Quicksort (Partition)
Pivot wählen
Kleiner als Pivot → linke Seite, größer → rechte Seite
Linke und rechte Teilarrays rekursiv sortieren
Instabil | In-place | Am häufigsten verwendet
Merge Sort (Merge)
Rekursiv halbieren bis zur kleinsten Einheit
Zwei geordnete Teilfolgen zusammenführen
Benötigt zusätzliches Array O(n)
Stabil | Benötigt zusätzlichen Speicher | Externes Sortieren
Heap Sort (Heapify)
Max-Heap aufbauen O(n)
Heap-Spitze (Maximum) ans Ende setzen
Heap neu anpassen O(log n)
Instabil? In-place O(1) | speicheroptimal
Vollständiger Vergleich von Sortieralgorithmen
| Algorithmus | Bestfall | Durchschnittlich | Worstfall | Speicher | Stabilität |
|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Stabil |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Instabil |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Stabil |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Instabil |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stabil |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Instabil |
| Shellsort | O(n log n) | O(n^1.3) | O(n²) | O(1) | Instabil |
Andere ErweiterungenPraktische Auswahlempfehlung: Für allgemeine Szenarien ist Quicksort die erste Wahl; wählen Sie Mergesort, wenn Stabilität benötigt wird; wählen Sie Heapsort, wenn der Speicher extrem begrenzt ist; wählen Sie Insertionsort für kleine Datenmengen oder nahezu sortierte Daten.