Was bedeutet es, dass ein Sortieralgorithmus „stabil“ ist?
43
Beim Lesen verschiedener Sortieralgorithmen wurde erwähnt, dass einige "stabil" sind und andere nicht. Was bedeutet das und welche Kompromisse sind auf dieser Basis bei der Auswahl eines Algorithmus zu beachten?
Dies ist eine Frage, zu der es an eigener Forschung mangelt. Beantwortet mit einem Wikipedia-Bild. Und es gibt wirklich gutes Feedback, was mich irgendwie traurig macht. IMHO sollte es geschlossen sein und keine Gegenstimmen bekommen.
Mare Infinitus
4
Andererseits habe ich das einfach gesehen und etwas Neues gelernt. Wenn ich gewusst hätte, dass ich das nicht wusste, hätte ich es recherchieren können, aber da das OP die Frage stellte, weiß ich jetzt, was ich nicht wusste, dass ich es nicht wusste.
Kazark
4
Im Allgemeinen sind "nur googeln" oder "auf Wikipedia nachschlagen" keine akzeptablen Antworten auf StackExchange-Websites. Weil sie keine Antwort darauf geben, was der Beschwerdeführer beim Aufruf an die Behörden von Google und Wikipedia als gültige Frage bestätigt. WENN die Frage leicht ein Duplikat einer anderen Frage oder Fragen innerhalb von programmers.stackexchange ist, können Sie sich beschweren.
Michael Paulukonis
Antworten:
88
Bei einer stabilen Sortierung wird die ursprüngliche Reihenfolge der Eingabemenge beibehalten, bei der der Vergleichsalgorithmus nicht zwischen zwei oder mehr Elementen unterscheidet.
Betrachten Sie einen Sortieralgorithmus, der Karten nach Rang sortiert , aber nicht nach Farbe. Die stabile Sortierung garantiert, dass die ursprüngliche Reihenfolge der Karten mit demselben Rang erhalten bleibt. die instabile Sorte wird es nicht.
Korrektur: Der instabile Algorithmus zeigt undefiniertes Verhalten, wenn zwei Elemente gleich sind. Es ist durchaus möglich, dass die Reihenfolge manchmal beibehalten wird.
@MareInfinitus: Es ist gemeinfrei. Überprüfen Sie die Zuordnung auf dem Originalbild.
Robert Harvey
2
Ein gutes Bild erklärt im Durchschnitt schneller und tiefer als viele Wörter. Rechtsfragen waren nicht das, worüber ich sprechen wollte.
Mare Infinitus
3
@RobertHarvey Eigentlich glaube ich, dass der Editor korrekt ist. In Ihrem Beitrag heißt es derzeit, dass eine stabile Sortierung die Reihenfolge der Karten in derselben Farbe beibehält, Karten in derselben Farbe jedoch unterschiedliche Ränge haben und daher neu angeordnet werden müssen, um eine sortierte Reihenfolge zu erreichen. Zum Beispiel behält die Sortierung die Reihenfolge der 2 und der 5 Herzen nicht bei. Es ist die Reihenfolge der Karten mit demselben Rang (und verschiedenen Farben), die den Unterschied zwischen stabil und instabil ausmacht.
David Z
26
Stabile Algorithmen behalten die relative Reihenfolge der Elemente bei.
Ein stabiler Sortieralgorithmus behält also die relative Reihenfolge der vergleichbaren Werte bei.
Stellen Sie sich einen Sortieralgorithmus vor, bei dem wir eine Sammlung von 2D-Punkten basierend auf ihrer X-Dimension sortieren.
Was den Kompromiss angeht ... Nun, eine stabile Sortierung ist weniger effizient, aber manchmal braucht man sie.
Wenn ein Benutzer beispielsweise auf eine Spaltenüberschrift klickt, um die Werte in einer Benutzeroberfläche zu sortieren, ist zu erwarten, dass seine vorherige Sortierreihenfolge bei gleichen Werten verwendet wird.
Ist es weniger effizient? Es scheint "offensichtlich", aber einige der besten Sortieralgorithmen sind von Natur aus stabil (z. B. alles, was auf Merge-Sortierung basiert, wie z. B. Tim-Sortierung). Sie müssen keine explizite zusätzliche Arbeit leisten, um stabil zu sein.
9
Stable hat generell nichts mit Performance zu tun. Mergesort läuft in O (n * log n) und ist stabil. Heapsort hat eine ähnliche Leistung, ist aber nicht stabil.
Mare Infinitus
2
"Stabil" kann auch für Datenstrukturen gelten, z. Ein "stabiler Heap" ist ein Heap, der Elemente mit derselben Priorität in derselben Reihenfolge aus der Warteschlange entfernt, in der sie in die Warteschlange gestellt wurden. Dies ist sehr wichtig für effiziente Pfadfindungsalgorithmen.
BlueRaja - Danny Pflughoeft
1
Es gibt keine stabilen Sortierungen, bei denen es sich um O (n ln n) -Vergleiche und auch um O (1) im Speicher handelt. Geschwindigkeit ist nicht das einzige Maß für Effizienz. Die Tatsache, dass Sie nicht stabil vor Ort sortieren können, spielt eine Rolle.
QuestionC
3
@QuestionC Es scheint Block Art ist stabil und passt diese Grenzen.
Antworten:
Bei einer stabilen Sortierung wird die ursprüngliche Reihenfolge der Eingabemenge beibehalten, bei der der Vergleichsalgorithmus nicht zwischen zwei oder mehr Elementen unterscheidet.
Betrachten Sie einen Sortieralgorithmus, der Karten nach Rang sortiert , aber nicht nach Farbe. Die stabile Sortierung garantiert, dass die ursprüngliche Reihenfolge der Karten mit demselben Rang erhalten bleibt. die instabile Sorte wird es nicht.
quelle
Stabile Algorithmen behalten die relative Reihenfolge der Elemente bei.
Ein stabiler Sortieralgorithmus behält also die relative Reihenfolge der vergleichbaren Werte bei.
Stellen Sie sich einen Sortieralgorithmus vor, bei dem wir eine Sammlung von 2D-Punkten basierend auf ihrer X-Dimension sortieren.
Sammlung sortiert werden:
{(6, 3), (5, 5), (6, 1), (1, 3)}Stabil sortiert:
{(1, 3), (5, 5), (6, 3), (6, 1)}Normal sortiert: Entweder
{(1, 3), (5, 5), (6, 3), (6, 1)}oder{(1, 3), (5, 5), (6, 1), (6, 3)}Was den Kompromiss angeht ... Nun, eine stabile Sortierung ist weniger effizient, aber manchmal braucht man sie.
Wenn ein Benutzer beispielsweise auf eine Spaltenüberschrift klickt, um die Werte in einer Benutzeroberfläche zu sortieren, ist zu erwarten, dass seine vorherige Sortierreihenfolge bei gleichen Werten verwendet wird.
quelle