Was ist Stabilität in Sortieralgorithmen und warum ist es wichtig?
Ich bin sehr neugierig, warum Stabilität ist oder ist nicht wichtig in der Sortier-algorithmen?
Kommentar zu dem Problem - Öffnen
Für die Parallelisierung Zwecke? Beispiel: merge-sort ist stabil und kann gut parallelisiert werden und so ist quicksort.
Klassische QuickSort instabil
stabile sort-algo -
IBM (Insertion, Bubble, Merge)
@roottraveller entschuldigen Sie mich?
InformationsquelleAutor der Frage DarthVader | 2009-10-05
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einen Sortier-Algorithmus wird gesagt, stabil, wenn zwei Objekte mit gleichen Tasten in der gleichen Reihenfolge angezeigt in sortierter Ausgabe, wie Sie in das Eingabe-array und sortiert werden. Einige Sortier-algorithmen sind stabil, von der Natur wie Insertion sort, Merge-Sort, Bubble-Sort, etc. Und einige Sortier-algorithmen sind nicht, wie Heap Sort, Quick Sort, etc..
Hintergrund: eine "stabile" Sortierung Algorithmus hält die Elemente mit gleichem Sortierschlüssel in Ordnung. Nehmen wir an, wir haben eine Liste von 5-Buchstaben-Wörter:
Wenn wir die Liste Sortieren, indem Sie einfach die ersten Buchstaben von jedem Wort dann ein Stall-Art produzieren würde:
In einem instabil - sort-Algorithmus,
straw
oderspork
können ausgetauscht werden, aber stabil sind, bleiben Sie in der gleichen relativen Positionen (das heißt, seitstraw
erscheint vorspork
in der Eingabe, es erscheint auch vorspork
in der Ausgabe).Konnten wir Sortieren die Liste der Wörter, die Verwendung dieses Algorithmus: stabile Sortierung nach Spalte 5, dann 4, dann 3, dann 2, dann 1.
In das Ende, wird es korrekt sortiert sein. Überzeugen Sie sich selbst. (übrigens, dieser Algorithmus wird als radix-Sortieren)
Nun Ihre Frage zu beantworten, nehmen wir an, wir haben eine Liste mit vor-und Nachnamen. Wir sind aufgefordert, zu Sortieren ", indem Sie Nachname, dann durch die erste". Wir konnten zuerst Sortieren (stabil oder instabil) durch den ersten Namen, dann stabil Sortieren Sie nach dem Nachnamen. Nach diesen sortiert, die Liste ist primär nach dem Nachnamen sortiert. Jedoch, wo die letzten sind die gleichen Namen, die Vornamen sortiert sind.
Können Sie nicht stapeln instabilen Sorten in der gleichen Art und Weise.
InformationsquelleAutor der Antwort Joey Adams
Einer stabilen Sortier-Algorithmus ist das eine, die Art der identischen Elemente in der gleichen Reihenfolge angezeigt, in der Eingabe, während instabile Sortierung kann nicht erfüllen, der Fall ist.
Stabile Sortier-Algorithmen:
Instabilen Sortier-Algorithmen:
InformationsquelleAutor der Antwort snr
Es hängt davon ab, was Sie tun.
Stell dir vor, du hast einige Leute die Datensätze mit einem ersten und einem Feld Nachname. Zuerst Sortieren Sie die Liste nach Vornamen. Wenn Sie dann Sortieren Sie die Liste mit einem stabilen Algorithmus von Nachnamen, haben Sie eine Liste, sortiert nach name UND Vorname.
InformationsquelleAutor der Antwort svens
Sortierung Stabilität bedeutet, dass Datensätze mit dem gleichen Schlüssel behalten Ihre relative Reihenfolge vor und nach dem Sortieren.
Also Stabilität ist, wichtig wenn, und nur wenn, das problem bist du die Lösung erfordert die Beibehaltung dieser relativen Ordnung.
Wenn Sie nicht brauchen Stabilität, Sie können mit einem schnellen, Speicher-schlürfen-Algorithmus aus einer Bibliothek, wie heapsort oder quicksort, und vergessen Sie es.
Wenn Sie Stabilität brauchen, ist es komplizierter. Stabile algorithmen haben höhere big-O CPU und/oder Speicher-Nutzung als instabile algorithmen. Also, wenn Sie haben ein großes DataSet, Sie haben die Wahl zwischen schlagen, bis die CPU oder der Speicher. Wenn Sie eingeschränkt auf beiden CPU-und Speicher, haben Sie ein problem. Ein guter Kompromiss stabilen Algorithmus ist ein binärer Baum Art; die Wikipedia-Artikel hat eine pathetisch einfache C++ - Implementierung, basierend auf dem STL.
Können Sie machen einen instabilen Algorithmus in einen Stall, indem Sie den ursprünglichen Datensatz, Zahl des letzten Platzes Schlüssel für jeden Datensatz.
InformationsquelleAutor der Antwort Bob Murphy
Es gibt ein paar Gründe, warum die Stabilität wichtig sein kann. Einer ist, dass, wenn zwei Datensätze müssen nicht getauscht werden, durch den Austausch von Ihnen, die Sie verursachen kann ein Speicher-update, eine Seite als fehlerhaft gekennzeichnet ist, und muss neu geschrieben werden auf der Festplatte (oder ein anderes langsames medium).
InformationsquelleAutor der Antwort Clinton Pierce
Einen Sortier-Algorithmus wird gesagt, stabil, wenn zwei Objekte mit gleichen Tasten in der gleichen Reihenfolge angezeigt in sortierter Ausgabe, wie Sie in der input unsortierten array. Einige Sortier-algorithmen sind stabil, von der Natur wie Insertion sort, Merge-Sort, Bubble-Sort, etc. Und einige Sortier-algorithmen sind nicht, wie Heap Sort, Quick Sort, etc..
Jedoch jedem gegebenen Sortier-algo, die nicht stabil ist, kann geändert werden, um stabil zu sein. Kann es sein, Sortier-algo spezifischen Möglichkeiten, um es stabil, aber im Allgemeinen, jeder Vergleich basiert Sortier-Algorithmus ist nicht stabil, durch die Natur kann geändert werden, um stabil durch das ändern der Schlüssel-Vergleich Betrieb, so dass der Vergleich der beiden Tasten hält die position als Faktor für Objekte mit gleichem Schlüssel.
Referenzen:
http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/Stabilität.pdf
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
InformationsquelleAutor der Antwort roottraveller
Wenn Sie annehmen, was Sie sind-Sortierung sind nur zahlen und nur Ihre Werte erkennen/unterscheiden (z.B. Elemente mit dem gleichen Wert sind identicle), dann den Stabilitäts-Problem der Sortierung ist bedeutungslos.
Jedoch Objekte mit gleicher Priorität in der Sortierung kann unterschiedlich sein, und irgendwann Ihre relative Reihenfolge ist sinnvoll, Informationen. In diesem Fall instabil Sortieren erzeugt Probleme.
Zum Beispiel, Sie haben eine Liste von Daten, welche enthält Kosten Zeit [T], in der alle Spieler zu reinigen, ein Labyrinth mit Ebene [L] in einem Spiel.
Nehmen wir an, wir brauchen, um die Rangfolge der Spieler, wie schnell Sie reinigen das Labyrinth. Jedoch, eine zusätzliche Regel gilt: Spieler, die reinigen Sie das Labyrinth mit einem höheren level haben immer einen höheren Rang bekommen, egal wie lange die Zeit Kosten.
Natürlich könnten Sie versuchen, zum anzeigen der gekoppelten Wert [T,L] in eine reelle Zahl [R] mit einigen algorithmen, die sich an die Regeln hält und dann Reihen sich alle Spieler mit dem [R] - Wert.
Jedoch, wenn stabile Sortierung möglich ist, dann können Sie einfach Sortieren Sie die gesamte Liste, indem Sie [T] (Schneller Spieler) und dann von [L]. In diesem Fall, die relative Reihenfolge der Spieler (von Zeit, Kosten) nicht geändert werden, nachdem Sie gruppiert nach der Höhe der Irrgarten Sie gereinigt.
PS: natürlich ist der Ansatz zu Sortieren, zweimal ist nicht die beste Lösung für das jeweilige problem, sondern zu erklären, die Frage der poster sollte es genug sein.
InformationsquelleAutor der Antwort M Ciel
Ich weiß, es gibt viele Antworten, aber zu mir, diese Antwort, durch Robert Harvey, fasste es sehr viel deutlicher:
Quelle
InformationsquelleAutor der Antwort John R Perry
Stabile Art immer wieder gleiche Lösung (permutation) auf denselben Eingang.
Etwa [2,1,2] sortiert werden mit stabilen Art als permutation [2,1,3] (Erster index 2 ist, dann ist index 1 und index 3 in sortierter Ausgabe) bedeutet, dass die Ausgabe immer gemischt gleiche Weise. Andere, nicht stabil, aber immer noch richtige permutation ist [2,3,1].
Quick sort ist nicht stabil Sortieren und permutation Unterschiede zwischen gleichen Elementen hängt von Algorithmus für die Kommissionierung pivot. Einige Implementierungen Holen nach dem Zufallsprinzip und das kann schnell sort nachgeben verschiedenen Permutationen auf gleiche Eingaben mit gleichen Algorithmus.
Stabilen Sortieralgorithmus notwendig ist deterministisch.
InformationsquelleAutor der Antwort Luka Rahne