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

(c) 2004 by RTC, www.linux-related.de
Dieses Dokument unterliegt der GNU Free Documentation License