Sortieren Flashcards
Sortieren
° Klassische Informatikaufgabe für Sammlungen
° Voraussetzung zum Sortieren ist eine Ordnungsrelation
° Algorithmen, nach denen Sammlungen sortiert werden = Sortierverfahren
Sortierverfahren
° Komplexität: Anzahl der Schritte um n Elemente zu ordnen (im besten/ durchschnittlichen/ schlechtesten Fall, abhängig von der Vorsortierung der Elemente)
° Speicherbedarf beim Sortieren: Wird kein zusätzlicher Speicherbedarf benötigt ist ein Sortierverfahren in place
° Stabilität: Ein Sortierverfahren ist stabil, wenn es die ursprüngliche Reihenfolge zweier gleicher Elemente beim Sortieren nicht verändert
° Art des Algorithmus: entweder vergleichsbasiert oder die Position in der Sortierung kann errechnet werden (z.B. Bucketsort, Radixsort)
Komplexität von Sortierverfahren
° Gesucht wird eine obere Schranke für die Anzahl von Schlüsselvergleichen, die im schlechtesten Fall notwendig sind, um n Objekte zu sortieren
g(n)= n(logn)+2
-> O(n log n): gute Verfahren
f(n)=n²
-> O (n²): einfache Verfahren
- > Ab einem bestimmten Punkt liegen die Werte der Funktion g immer unter denen von f
- > Bis zu diesem Punkt kann der Aufwand der Funktion f geringer sein, obwohl sie die Funktion g für große n dominiert
Prinzipien von vergleichsbasierten Sortierverfahren
° Vertauschen: Vertauschte Einträge, wenn sie wechselseitig falsche angeordnet sind (Bubble-Sort, Shaker-Sort)
° Einfügen: Selle eine sortiere Teilfolge her und füge die verbleibenden Elemente an der richtigen Stelle ein (Insertion-Sort, Shell-Sort)
° Auswahl: Suche das Element, das an Platz 1 gehört, an Platz 2 usw (Selection-Sort, Heap-Sort)
° In allen Fällen sind die Grundoperationen Vergleich zweier Elemente und Bewegen eines Elementes erforderlich
Bubble-Sort (Vertauschen)
° Vergleicht zwei benachbarte Elemente und vertauscht sie, falls sie in der falschen Reihenfolge vorliegen
° Wird solange wiederholt, bis keine Vertauschungen mehr nötig sind
° Hierzu sind in der Regel mehrere Durchläufe erforderlich
° Elemente steigen wie Blasen im Wasser auf (daher der Name)
Implementationsskizze Bubble-Sort
Für eine Liste L mit n Elementen:
Schleife über durchlauf = 1 .. n-1
{
Schleife über position = 1 .. n - durchlauf
{
Falls L[position] > L[position+1] …
{
… vertausche L[position] und L[position+1]
}
}
}
° Komplexität: Der Algorithmus besitzt eine quadratische Komplexität (O(n²)) und ist daher langsamer als viele andere Sortieralgorithmen
° Vorteile:
- Geringer Speicherbedarf (in-place-Verfahren), (potenziell) stabil
- Einfach und für kleine Elementmengen gut geeignet
Quicksort
° schneller, rekursiver, nicht-stabiler Sortieralgorithmus nach dem Prinzip Teile und Herrsche)
° Prinzip:
1. Ein beliebiger Schlüssel x wird aus den Elementen der zu sortierenden Reihe ausgewählt (Pivot-Element)
2. Die Reihe wird anschließend in eine Reihe mit Schlüsseln > x und eine mit Schlüsseln < x zerlegt (Divide-Schritt)
3. Beide resultierenden Teilreihen müssen um mindestens ein Element kleiner sein als die zu sortierende Reihe und werden rekursiv bis auf Elementebene in gleicher Weise behandelt (Conquer)
4. Die miteinander verketteten Teilreihen bilden insgesamt eine sortierte Gesamtreihe
Wahl des Pivotelements
° Idealerweise sollte der Median gewählt werden
° Wählt man bei einer bereits sortierten Reihe immer das linke Element als Pivot, wird in jedem Rekursionsschritt die Reihe nur um ein Element verkürzt
° Komplexität:
Durchschnitt: O(n log n)
Worst case: O(n²)
° Wenn die Implementierung es zulässt(schneller Indexzugriff), sollte deshalb das räumliche mittlere Element gewählt werden, um eine Degeneration auszuschließen
° Quicksort ist eines der schnellsten Sortierverfahren und leicht zu implementieren
O(n²) vs. O(n log n)
O(n log n) -> ist bei großen Datenmengen schneller!
Sortieren mit linearer Ordnung
° Voraussetzungen:
- Die menge aller Schlüssel ist hinreichend klein
- Es muss nicht ‘in situ’ sortiert werden
° Das Verfahren ist linear in n, da der Aufwand für das Durchlaufen der Ausgangsliste und des Schlüssel-Arrays linear von der Zahl der Listenelemente abhängt
° Sortieren mit Buckert-Sort:
- Lege für jeden Schlüssel eine Liste an
- Mache die Listen zu Elementen eines Arrays, das mit dem Schlüssel indiziert werden kann
- Gehe die zu sortierenden Elemente einzeln durch und hänge jedes an die zu seinem Schlüssel gehörige Liste am
- Verbinde die Listen zu einer Ergebnisliste
