algorithm
Sortierung
Suche…
Parameter
| Parameter | Beschreibung |
|---|---|
| Stabilität | Ein Sortieralgorithmus ist stabil, wenn nach dem Sortieren die relative Reihenfolge der gleichen Elemente beibehalten wird. |
| An Ort und Stelle | Ein Sortieralgorithmus ist an Ort und Stelle , wenn sie nur unter Verwendung von Sorten O(1) Hilfsspeicher (nicht das Array zu zählen , die sortiert werden muss). |
| Bester Fall Komplexität | Ein Sortieralgorithmus hat eine Zeitkomplexität im besten Fall von O(T(n)) wenn seine Laufzeit mindestens T(n) für alle möglichen Eingaben beträgt. |
| Durchschnittliche Fallkomplexität | Ein Sortieralgorithmus hat eine durchschnittliche Fallzeitkomplexität von O(T(n)) wenn seine Laufzeit, gemittelt über alle möglichen Eingaben , T(n) . |
| Worst-Case-Komplexität | Ein Sortieralgorithmus hat eine ungünstigste Zeitkomplexität von O(T(n)) wenn seine Laufzeit höchstens T(n) beträgt. |
Stabilität beim Sortieren
Stabilität beim Sortieren bedeutet, ob ein Sortieralgorithmus die relative Reihenfolge der Gleichheitsschlüssel der ursprünglichen Eingabe in der Ergebnisausgabe beibehält.
Ein Sortieralgorithmus gilt als stabil, wenn zwei Objekte mit gleichen Schlüsseln in der sortierten Ausgabe in derselben Reihenfolge erscheinen, wie sie im unsortierten Eingabefeld erscheinen.
Betrachten Sie eine Liste von Paaren:
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
Nun werden wir die Liste mit dem ersten Element jedes Paares sortieren.
Bei einer stabilen Sortierung dieser Liste wird die folgende Liste ausgegeben:
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
Denn (9, 3) erscheint auch nach (9, 7) in der ursprünglichen Liste.
Bei einer instabilen Sortierung wird die folgende Liste ausgegeben:
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
Bei der instabilen Sortierung wird möglicherweise dieselbe Ausgabe wie bei der stabilen Sortierung generiert, jedoch nicht immer.
Bekannte stabile Sorten:
Bekannte instabile Sorten: