Zeitoptimale Sortierverfahren
Von Matthias Jauernig
und Tobias Hammerschmidt
Inhaltsverzeichnis
1. Einleitung
1.1 Grundgedanke
1.2 Anliegen/Ziele
1.3 Spielregeln
2. Quicksort
2.1 Historie/Hintergrund
2.2 Der Algorithmus
2.3 Zur programmiertechnischen Realisierung
2.4 Ein Beispiel
2.5 Verbesserungen
2.5.1 Median-of-three
2.5.2 Behandlung kleiner Teilfelder
2.5.3 Optimale Wahl von M
2.5.4 Beides zusammen?
2.6 Laufzeitbetrachtungen
3. Mergesort
3.1 Historie/Hintergrund
3.2 Der Algorithmus
3.3 Zur programmiertechnischen Realisierung
3.3.1 Rekursiv
3.3.2 Iterativ
3.4 Ein Beispiel zu rekursivem Mergesort
3.5 Analyse der Leistungsfähigkeit
4. Heapsort
4.1 Hintergrund
4.2 Die Datenstruktur Heap
4.2.1 Grundlagen
4.2.2 Heapordnungen
4.2.2.1 MaxHeap
4.2.2.2 MinHeap
4.2.3 Die Operation "Versickern"
4.2.4 Aufbauen eines Heaps
4.3 Der Heapsort-Algorithmus
4.4 Zur programmiertechnischen Realisierung
4.5 Laufzeitbetrachtungen
5. Radixsort
5.1 Hintergrund
5.2 Bit-Operationen
5.3 Radix Exchange Sort
5.4 Bucketsort
5.5 Straight Radix Sort
5.6 Lineares Sortieren
5.7 Laufzeitbetrachtungen
6. Schlussbemerkungen
6.1 Fazit
6.2 Quellennachweis/Buchempfehlungen
6.3 Downloads
6.4 Kontakt