Sorting Algorithm
Sortieralgorithmen bringen Elemente in eine Reihenfolge — Quicksort, Mergesort und Heapsort sind verbreitet — mit Komplexitäten von O(n log n) bis O(n²).
Zweck
Unsortierte Daten ordnen, die Grundlage für Suche, Deduplizierung und Anzeige.
Mechanismus
Vergleichsbasiertes Sortieren hat eine untere Schranke von O(n log n). Quicksort im Mittel O(n log n), schlimmster Fall O(n²), in-place. Mergesort ist O(n log n), stabil, braucht aber O(n) Platz. Heapsort ist O(n log n) in-place. Counting-/Radixsort sind nicht vergleichsbasiert und können O(n) erreichen. Stabile Sortierungen erhalten die relative Reihenfolge gleicher Elemente.
Anwendungsfälle
- ORDER BY in Datenbanken
- Vorverarbeitung vor der Suche
- Rankings und Bestenlisten
- Deduplizierung (Sortieren + Nachbarvergleich)
Beispiele
- Eingabe
[3,1,4,1,5] → quicksortOutput[1,1,3,4,5]O(n log n) average
Häufige Fehler
- Quicksort recursion overhead is high for small arrays
- Use insertion sort for small arrays (a quicksort optimization)
Verwandte Begriffe
Big O Notation
Die Big-O-Notation beschreibt die asymptotische obere Schranke einer Funktion und dient der Analyse der Zeit-/Speicherkomplexität von Algorithmen unter Vernachlässigung von Konstanten und niedrigeren Termen. GLOSSAR
Binary Search
Die binäre Suche vergleicht mit dem mittleren Element eines sortierten Arrays und halbiert den Bereich jedes Mal, wodurch ein Ziel in O(log n) gefunden wird; sie ist der grundlegende effiziente Suchalgorithmus. GLOSSAR
Hash Table
Eine Hashtabelle bildet Schlüssel über eine Hashfunktion auf ein Bucket-Array ab und bietet im Schnitt O(1) bei Suche/Einfügen/Löschen; sie gehört zu den meistgenutzten Datenstrukturen. GLOSSAR