Sortieralgorithmen

Sortieralgorithmen

1. Einfache Verfahren

   • SelectionSort
     • intern/extern?
       • intern
     • Effizienz
       • O(n²)
     • in situ
       • ja
     • Methode
       • Auswahl
         • des jeweils kleinsten Elements
     • stabil?
       • Grundform Nein
   • InsertionSort
     • Methode
       • durch Einfügen
         • des jeweiligen Elements an der richtigen Stelle
     • intern/extern
       • intern
     • Effizienz
       • O(n²)
     • in situ?
       • ja
     • stabil?
       • ja
   • BubbleSort
     • Vertauschen
       • benachbarter Elemente

2. Divide and Conqr

   • MergeSort
     • Methode
       • Divide
         • Array mittig in zwei Hälften teilen
       • Conquer
         • rekursiver Aufruf von Merge-Sort
       • Merge
         • beide Teile (wie ein Reißverschluss) zusammenführen
           • aus beiden sortierten Teillisten vom Beginn an
           • immer das Element wählen, das kleiner ist
           • dieses dann an Ergebnisliste anhängen
           • Anfangszeiger dieser Teil-Liste eins weiter setzen
     • intern/extern
       • eher extern
     • Effizienz
       • worst
         • O (n log n)
       • avg
         • O (n log n)
     • in situ?
       • nein
     • stabil?
       • ja
   • Quicksort
     • Methode
       • Divide
         • Pivotelement "x" wählen
           • dann Array Aufteilen in
             • Teil < x
             • Teil >= x
       • Conquer
         • für jeden Teil wieder rekursiv Algorithmus anwenden
       • Merge
         • sortiere Teillisten concatenieren
     • intern / extern?
       • ja
     • Effizienz
       • worst-case
         • O(n²)
       • Avg-Case
         • O (n log n)
     • in situ?
       • Ja
     • stabil?
       • Nein
     • clever-Quicksort

3. Fachverteilen

   • Bucket-Sort
     • Methode
       • jedes Fach sortieren
         • z.B. mit Merge-Sort
       • danach Fächer konkatenieren
       • Partitionieren
         • Verteilen der Elemente auf n Fächer
     • Laufzeit
       • O(n), wenn gleichverteilt
     • in situ?
       • nein
     • intern/extern?
       • intern
     • stabil?
       • abhängig vom Sortierfahren der einzelnen Buckets
   • Radix-Sort
     • Methode
       • wiederholtes stellenweises Bucketsort
         • Für jede Stelle
           • Partitionierungsphase
             • Elemente auf Buckets verteilen
           • Sammelphase
             • Fächer der Reihe nach wieder einsammeln
     • MSD Radixsort
       • Bucketsort, bei dem jedes Bucket mit Bucketsort sortiert wird
   • Voraussetzungen
     • Elemente möglichst gleich verteilt
     • wenig Elemente mit gleichem Schlüssel

4. Allgemeines

   • Klassifizierungen
     • intern/extern ?
       • intern
         • kann komplett im Hauptspeicher gehalten werden
       • extern
         • nur Teile im Hauptspeicher gehalten
     • methodisch
       • Einfügen / Auswählen
       • Divide and Conquer
       • Fachverteilen
     • Effizienz / Laufzeit
       • quadratisch
         • O(n²)
       • linear
         • O(n)
       • gute Sortierverfahren
         • O(n log(n))
     • in situ (place)
       • direkt im Array möglich
       • oder nicht
   • Sortierverfahren stabil
     • wenn Werte mit gleichem Schlüssel
     • Position behalten

5. verfeinerte Verfahren

   • Auswählen
     • Heapsort
       • stabil?
         • Nein
       • Methode
         • Aufbau eines Heaps
         • nacheinander Wurzel entnehmen
         • danach Heap wieder herstellen
           • letztes Element kommt in Wurzel
           • reheap: bis zur richtigen Position einsickern lassen
       • Effizienz
         • O (n log n)
       • in situ?
         • möglich
           • mit Arrays
     • bottom-up Heapsort
   • Einfügen
     • Baumsortieren
       • stabil?
         • nein
       • Methode
         • Binären Suchbaum erstellen
           • danach In-Order-Durchlauf
             • leftChild, aktuelles Element, right Child
       • Effizienz
         • O(n log n)
       • in situ?

Bilder und Dateien der Mindmap