3 - Sortieren

Auf der Menge ist strenge, schwache Ordnung definiert (“kleiner gleich”)

• zugrundeliegende Datenstruktur: Felder oder verkettete Listen

• Laufzeitkomplexität: Anzahl Vergleichs- und Vertauschungsoperationen in Abhängigkeit der Problemgröße

• Zusätzlicher Speicherbedarf

  • in-place: nur Speicher der Eingabedaten verwendet

  • out-of-place: zusätzlicher Speicher benötigt

• Stabilität: Erhalt der relativen Reihenfolge von Elementen, die bzgl. der Ordnung gleichwertig sind

  • instabil

  • stabil

• Insertionsort

• Selectionsort

• Bubblesort

• Suche kleinstes (bzw. größtes) Element

• Vertausche es mit dem ersten Element im unsortierten Bereich

• schrittweise Erweiterung des sortierten Bereichs

• Definieren des ersten Elements als “sortiert”

• Einfügen jedes weiteren Werts an richtige Stelle in sortierten Bereich

• schrittweise Erweiterung des sortierten Bereichs

• Vergleiche von links nach rechts zwei Nachbarelemente und vertausche, falls Reihenfolge inkorrekt

• Wiederhole solange, bis keine Vertauschung mehr nötig

• Unsortierter Bereich wird bei jeder Wiederholung von rechts um ein Element verkleinert

a) Insertionsort

b) Selectionsort

c) Bubblesort

• Quicksort

• Mergesort

• Heapsort

• nutzt Teile-und-Herrsche Prinzip

• Aufteilen des zu sortierenden Datensatzes in zwei kleinere Datensätze, die individuell sortiert werden

• Verschmelzen der sortierten, kleinen Datensätze

• rekursive Anwendung (ggf. erneute Aufteilung der kleineren Datensätze)

• speicherintensiv

• nutzt Teile-und-Herrsche Prinzip

• Wählen eines Pivotelements

• Partitionierung des Datensatzes anhand des Pivotelements

  • alle kleineren Elemente nach links, alle größeren nach rechts

• rekursive Anwendung

• speichersparend

• gutes Allzweckverfahren

• Komplexität: 0(n log n)

• Laufzeit steigt in Richtung 0(n2), wenn

  • Partitionierung dauerhaft asymmetrisch

  • Werte sich nur wenig unterscheiden

    
    

• iterative Implementierung

• Steigerung der Partitionssymmetrie

• Kombination mit Insertionsort

  • kleinere Teilfelder ignorieren

  • mit Insertionsort sortieren

• Verwendung von binärem Heap als zentrale Datenstruktur

• Ablauf

  • Eingabearray in gültige (Max-)Heap-Reihenfolge bringen

    • Vertauschen des Wurzel Elements (=größtes Element) mit letztem Element

    • Der um ein Element verkleinerte Heap korrigiert

• Ergebnis: sortiertes Feld von Elementen

A) Quicksort

B) Quicksort

C) Mergesort

D) Heapsort

• Countingsort

• Bucketsort

• Radixsort

• nicht vergleichs-, sondern adressbasiert

• ermöglicht Sortieren mit linearer Laufzeit, die von Länge der Eingabe n und Anzahl der möglichen Werte k abhängt

• anwendbar, wenn Sortierschlüssel natürliche Zahlen aus einem beschränktem Intervall mit k möglichen Werten sind

• Ablauf

  • Zählen der Vorkomnisse der Schlüsselwerte

  • Berechnung der Adresse bzw. Position im sortierten Array

  • Einfügen der Werte an der richtigen Position

• anwendbar, wenn Sortierschlüssel reele Zahlen aus beschränktem intervall

• Laufzeit: abhängig von Verteilung der Schlüsselwerte in der Eingabe

• Ablauf

  • Verteilung der Elemente auf die Eimer

  • Sortierung der Elemente innerhalb der Eimer mit beliebigem (optimalem) Sortierverfahren

  • Zusammenfügen der Inhalte der Eimer

• nicht-vergleichsbasiertes Sortierverfahren, das auf Countingsort oder Bucketsort basiert

• anwendbar, wenn Schlüssel bekannte maximale Länge l aufweisen

• Ablauf

  • Erstelle einen Behälter für jeden möglichen Wert der Basis

  • Für jede Stelle des Schlüssels, beginnend mit der letzten Stelle

    • Verschiebe jedes Element der Liste in den entsprechenden Behälter

    • Entnehme die Elemente aus dem Behälter und hänge sie der Liste an. Durchlaufe die Behäklter entsprechend der Sortierfunktion

a) Bucket Sort?

b) Counting Sort

c) lexikographisch