Sortieralgorithmen

Einfache Verfahren
1. SelectionSort
  1. intern/extern?
    1. intern
  2. Effizienz
    1. O(n²)
  3. in situ
    1. ja
  4. Methode
    1. Auswahl
      1. des jeweils kleinsten Elements
  5. stabil?
    1. Grundform Nein
2. InsertionSort
  1. Methode
    1. durch Einfügen
      1. des jeweiligen Elements an der richtigen Stelle
  2. intern/extern
    1. intern
  3. Effizienz
    1. O(n²)
  4. in situ?
    1. ja
  5. stabil?
    1. ja
3. BubbleSort
  1. Vertauschen
    1. benachbarter Elemente
Divide and Conqr
1. MergeSort
  1. Methode
    1. Divide
      1. Array mittig in zwei Hälften teilen
    2. Conquer
      1. rekursiver Aufruf von Merge-Sort
    3. Merge
      1. 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
  2. intern/extern
    1. eher extern
  3. Effizienz
    1. worst
      1. O (n log n)
    2. avg
      1. O (n log n)
  4. in situ?
    1. nein
  5. stabil?
    1. ja
2. Quicksort
  1. Methode
    1. Divide
      1. Pivotelement "x" wählen
        dann Array Aufteilen in
        Teil < x
        Teil >= x
    2. Conquer
      1. für jeden Teil wieder rekursiv Algorithmus anwenden
    3. Merge
      1. sortiere Teillisten concatenieren
  2. intern / extern?
    1. ja
  3. Effizienz
    1. worst-case
      1. O(n²)
    2. Avg-Case
      1. O (n log n)
  4. in situ?
    1. Ja
  5. stabil?
    1. Nein
  6. clever-Quicksort
Fachverteilen
1. Bucket-Sort
  1. Methode
    1. jedes Fach sortieren
      1. z.B. mit Merge-Sort
    2. danach Fächer konkatenieren
    3. Partitionieren
      1. Verteilen der Elemente auf n Fächer
  2. Laufzeit
    1. O(n), wenn gleichverteilt
  3. in situ?
    1. nein
  4. intern/extern?
    1. intern
  5. stabil?
    1. abhängig vom Sortierfahren der einzelnen Buckets
2. Radix-Sort
  1. Methode
    1. wiederholtes stellenweises Bucketsort
      1. Für jede Stelle
        Partitionierungsphase
        Elemente auf Buckets verteilen
        Sammelphase
        Fächer der Reihe nach wieder einsammeln
  2. MSD Radixsort
    1. Bucketsort, bei dem jedes Bucket mit Bucketsort sortiert wird
3. Voraussetzungen
  1. Elemente möglichst gleich verteilt
  2. wenig Elemente mit gleichem Schlüssel
Allgemeines
1. Klassifizierungen
  1. intern/extern ?
    1. intern
      1. kann komplett im Hauptspeicher gehalten werden
    2. extern
      1. nur Teile im Hauptspeicher gehalten
  2. methodisch
    1. Einfügen / Auswählen
    2. Divide and Conquer
    3. Fachverteilen
  3. Effizienz / Laufzeit
    1. quadratisch
      1. O(n²)
    2. linear
      1. O(n)
    3. gute Sortierverfahren
      1. O(n log(n))
  4. in situ (place)
    1. direkt im Array möglich
    2. oder nicht
2. Sortierverfahren stabil
  1. wenn Werte mit gleichem Schlüssel
  2. Position behalten
verfeinerte Verfahren
1. Auswählen
  1. Heapsort
    1. stabil?
      1. Nein
    2. Methode
      1. Aufbau eines Heaps
      2. nacheinander Wurzel entnehmen
      3. danach Heap wieder herstellen
        letztes Element kommt in Wurzel
        reheap: bis zur richtigen Position einsickern lassen
    3. Effizienz
      1. O (n log n)
    4. in situ?
      1. möglich
        mit Arrays
  2. bottom-up Heapsort
2. Einfügen
  1. Baumsortieren
    1. stabil?
      1. nein
    2. Methode
      1. Binären Suchbaum erstellen
        danach In-Order-Durchlauf
        leftChild, aktuelles Element, right Child
    3. Effizienz
      1. O(n log n)
    4. in situ?

Next up

Sortieralgorithmen

Description

Resource summary

Media attachments

Similar

	Created by David Bratschke about 5 years ago