Sortierverfahren
Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Menge von Werten zu sortieren. Voraussetzung ist, dass auf den Werten eine totale Ordnung existiert, etwa die alphabetische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. Die Folge liegt üblicherweise in Form eines Arrays vor.Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten. Die Komplexität eines Algorithmus, also die Anzahl der nötigen Operationen, wird üblicherweise in der Landau-Notation dargestellt. Einige Sortierverfahren benötigen außerdem neben dem zur Speicherung des Arrays nötigen noch weiteren Speicherplatz. Komplexität und Speicherbedarf hängen bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bester Fall), Average Case (Durchschnittsverhalten) und Worst Case (schlechtester Fall).
Man unterscheidet zudem zwischen stabilen und instabilen Sortierverfahren sowie zwischen solchen, die in-place arbeiten, d.h. die ohne zusätzlichen Speicherplatz funktionieren, und solchen, die dies nicht tun.
Table of contents |
2 Beweis der unteren Schranke für vergleichsbasiertes Sortieren 3 Nicht-vergleichsbasiertes Sortieren 4 Sortierung nach Beziehungen |
Sortierverfahren | Komplexität | stabil | zusätzlicher Speicherbedarf |
Binarytreesort | O(n·log(n)) | ja | O(n) |
Bogosort | O(n!) | nein | O(n) |
Bubblesort | O(n2) | ja | - |
Cocktailsort (ShakerSort) | O(n2) | ja | - |
Combsort | O(n·log(n)) | nein | - |
Heapsort | O(n·log(n)) | nein | - |
Insertionsort | O(n2) | ja | - |
Introsort | O(n·log(n)) | nein | - |
Mergesort | O(n·log(n)) | ja | bei Arrays: O(n) |
Quicksort | O(n·log(n)), im Worst Case O(n2) | nein | - |
Selectionsort | O(n2) | nein | - |
Shellsort | O(n·log(n)2) | ja | - |
Smoothsort | O(n·log(n)) | nein | - |
Sei B der Entscheidungsbaum für die Zahlenfolge X (x1,....,xn). Da alle Permutationen von X das Ergebnis des Sortieralgorithmus sein könnten, muss der Entscheidungsbaum B mindestens n! Blätter haben.
Da eine Mindestanzahl von Schritten gesucht ist, treten im Entscheidungsbaum keine unnötigen Vergleiche auf.
In einem Entscheidungsbaum mit n! Blättern beträgt die maximale und die mittlere Tiefe eines Blattes mindestens log(n!).
Da eine untere Schranke gesucht ist, kann n! mittels nach unten hin abgeschätzt werden. Damit gilt .
Es bleibt noch zu zeigen, dass in einem Binärbaum mit k Blättern die maximale und die mittlere Tiefe eines Blattes mindestens log(k) beträgt. Angenommen B sei ein Binärbaum für welchen die obige Aussage nicht gilt. Seien T1 und T2 Teilbäume eines Binärbaumes mit k>2 Blättern. Für die Anzahl der Blätter k1 in T1 bzw. k2 in T2 gilt nun offensichtlich k1 < k, k2 < k und k1+k2 =k.
Für die Tiefe jedes Blattes, bezogen auf die Wurzel von B, gilt:
Das Minimum dieser Funktion liegt nun bei k1 + k2 = k und k1 = k2 = k/2. Eingesetzt in obige Formel ergibt das:
.
Dies ergibt einen Widerspruch zur Annahme, womit obige Aussage bewiesen wäre.Beweis der unteren Schranke für vergleichsbasiertes Sortieren
Es lässt sich beweisen, dass ein vergleichsbasiertes Sortierverfahren nicht schneller als sein kann:
Sortierverfahren | Komplexität | stabil | zusätzlicher Speicherbedarf |
Bucketsort | O(n+k) | ja | O(n+k) |
Countingsort | O(m+n) | ja | - |
Radixsort | O(n·log(k)) | nein | O(n) |
Sortierung nach Beziehungen
Wenn nicht mehr nach Eigenschaften, sondern nur noch nach paarweisen Beziehungen sortiert werden kann, so spricht man von einer topologischen Sortierung. Dies ist beispielsweise der Fall, wenn Aufgaben erledigt werden müssen, manche Aufgaben aber unbedingt vor anderen durchzuführen sind, bei anderen jedoch die Reihenfolge keine Rolle spielt.
For das topologische Sortieren gibt es Algorithmen, deren Laufzeit von der Anzahl der Beziehungen O(m) abhängt. Topologisches Sortieren ist nicht möglich, wenn gegenseitige (zyklische) Abhängikgkeiten bestehen. Eine topologische Sortierung muss nicht eindeutig sein.
Wenn die Beziehungen vollständig sind, also für je zwei Objekte eine Abhängigkeit vorgegeben ist, so geht die topologische Sortierung in eine gewöhnliche Sortierung über. Das Laufzeitverhalten der Algorithmen bei n Objekten ist dann O(n2).