Ich bin sehr gespannt, warum Stabilität beim Sortieren von Algorithmen wichtig ist oder nicht.
algorithm
sorting
language-agnostic
stability
Darth Vader
quelle
quelle
IBM (Insertion, Bubble, Merge)Antworten:
Ein Sortieralgorithmus gilt als stabil, wenn zwei Objekte mit gleichen Schlüsseln in der sortierten Ausgabe in derselben Reihenfolge erscheinen wie im zu sortierenden Eingabearray. Einige Sortieralgorithmen wie Insertion Sort, Merge Sort, Bubble Sort usw. sind von Natur aus stabil. Einige Sortieralgorithmen wie Heap Sort, Quick Sort usw. sind dies nicht.
Hintergrund : Ein "stabiler" Sortieralgorithmus hält die Elemente mit demselben Sortierschlüssel in der richtigen Reihenfolge. Angenommen, wir haben eine Liste mit Wörtern aus 5 Buchstaben:
Wenn wir die Liste nur nach dem ersten Buchstaben jedes Wortes sortieren, ergibt eine stabile Sortierung:
In einem instabilen Sortieralgorithmus
strawodersporkkönnen ausgetauscht werden, aber in einem stabilen bleiben sie an den gleichen relativen Positionen (das heißt, da siestrawzuvorsporkin der Eingabe erscheinen, erscheinen sie auch vorhersporkin der Ausgabe).Wir könnten die Liste der Wörter mit diesem Algorithmus sortieren: stabile Sortierung nach Spalte 5, dann 4, dann 3, dann 2, dann 1. Am Ende wird sie korrekt sortiert. Überzeugen Sie sich davon. (Dieser Algorithmus heißt übrigens Radix-Sortierung)
Angenommen, wir haben eine Liste mit Vor- und Nachnamen, um Ihre Frage zu beantworten. Wir werden gebeten, "nach Nachnamen, dann nach Vornamen" zu sortieren. Wir könnten zuerst (stabil oder instabil) nach dem Vornamen und dann stabil nach dem Nachnamen sortieren. Nach diesen Sortierungen wird die Liste hauptsächlich nach dem Nachnamen sortiert. Wenn jedoch die Nachnamen identisch sind, werden die Vornamen sortiert.
Sie können instabile Sortierungen nicht auf dieselbe Weise stapeln.
quelle
strawundsporkvergleiche gleich. Eine stabile Sortierung behält die Reihenfolge der Eingabe bei, während eine instabile Sortierung diese Garantie nicht übernimmt. "Richtig" hängt von der Anwendung ab. Mit der Sortierfunktion in den meisten Programmiersprachen kann der Benutzer eine benutzerdefinierte Bestellfunktion bereitstellen. Wenn die Benutzerfunktion verschiedene Elemente als gleich behandelt (z. B. gleichen Vornamen, unterschiedlichen Nachnamen), ist es hilfreich zu wissen, ob die ursprüngliche Reihenfolge beibehalten wird. Ein Beispiel aus der Praxis finden Sie in den Array-Sortierfunktionen von OCaml .Ein stabiler Sortieralgorithmus ist derjenige, der die identischen Elemente in derselben Reihenfolge sortiert, in der sie in der Eingabe erscheinen, während eine instabile Sortierung den Fall möglicherweise nicht erfüllt. - Ich danke meinem Algorithmus-Dozenten Didem Gozupek für den Einblick in Algorithmen .
Stabile Sortieralgorithmen:
Instabile Sortieralgorithmen:
quelle
Sortierstabilität bedeutet, dass Datensätze mit demselben Schlüssel ihre relative Reihenfolge vor und nach dem Sortieren beibehalten.
Stabilität ist also nur dann wichtig, wenn das Problem, das Sie lösen, die Beibehaltung dieser relativen Reihenfolge erfordert.
Wenn Sie keine Stabilität benötigen, können Sie einen schnellen Algorithmus zum Löschen des Speichers aus einer Bibliothek wie Heapsort oder Quicksort verwenden und diesen vergessen.
Wenn Sie Stabilität brauchen, ist es komplizierter. Stabile Algorithmen haben eine höhere Big-O-CPU- und / oder Speicherauslastung als instabile Algorithmen. Wenn Sie also einen großen Datensatz haben, müssen Sie zwischen dem Hochfahren der CPU oder des Speichers wählen. Wenn Sie sowohl die CPU als auch den Arbeitsspeicher einschränken, liegt ein Problem vor. Ein guter kompromissstabiler Algorithmus ist eine binäre Baumsortierung. Der Wikipedia-Artikel enthält eine pathetisch einfache C ++ - Implementierung, die auf der STL basiert.
Sie können einen instabilen Algorithmus in einen stabilen Algorithmus verwandeln, indem Sie die ursprüngliche Datensatznummer als Schlüssel für den letzten Platz für jeden Datensatz hinzufügen.
quelle
Es hängt davon ab, was Sie tun.
Stellen Sie sich vor, Sie haben einige Personendatensätze mit einem Vor- und einem Nachnamenfeld. Zuerst sortieren Sie die Liste nach Vornamen. Wenn Sie dann die Liste mit einem stabilen Algorithmus nach Nachnamen sortieren, wird eine Liste nach Vorname UND Nachname sortiert.
quelle
Es gibt einige Gründe, warum Stabilität wichtig sein kann. Zum einen können Sie eine Speicheraktualisierung verursachen, wenn zwei Datensätze nicht durch Austauschen ausgetauscht werden müssen. Eine Seite ist als fehlerhaft markiert und muss auf die Festplatte (oder ein anderes langsames Medium) neu geschrieben werden.
quelle
Ein Sortieralgorithmus gilt als stabil, wenn zwei Objekte mit gleichen Schlüsseln in der sortierten Ausgabe in derselben Reihenfolge erscheinen wie im unsortierten Eingabearray. Einige Sortieralgorithmen wie Insertion Sort, Merge Sort, Bubble Sort usw. sind von Natur aus stabil. Einige Sortieralgorithmen wie Heap Sort, Quick Sort usw. sind dies nicht.
Jedes gegebene Sortieralgo, das nicht stabil ist, kann jedoch so modifiziert werden, dass es stabil ist. Es kann algo-spezifische Möglichkeiten geben, um es stabil zu machen, aber im Allgemeinen kann jeder vergleichsbasierte Sortieralgorithmus, der von Natur aus nicht stabil ist, durch Ändern der Schlüsselvergleichsoperation so geändert werden, dass er stabil ist, so dass der Vergleich zweier Schlüssel die Position als a betrachtet Faktor für Objekte mit gleichen Schlüsseln.
Referenzen: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
quelle
Ich weiß, dass es dafür viele Antworten gibt, aber für mich hat diese Antwort von Robert Harvey sie viel klarer zusammengefasst:
Quelle
quelle
Wenn Sie annehmen, dass das, was Sie sortieren, nur Zahlen sind und nur ihre Werte sie identifizieren / unterscheiden (z. B. Elemente mit demselben Wert sind identisch), ist das Stabilitätsproblem der Sortierung bedeutungslos.
Objekte mit der gleichen Priorität beim Sortieren können jedoch unterschiedlich sein, und manchmal ist ihre relative Reihenfolge eine aussagekräftige Information. In diesem Fall führt eine instabile Sortierung zu Problemen.
Zum Beispiel haben Sie eine Liste von Daten, die die Zeitkosten [T] aller Spieler enthält, um ein Labyrinth mit Level [L] in einem Spiel zu reinigen. Angenommen, wir müssen die Spieler danach ordnen, wie schnell sie das Labyrinth reinigen. Es gilt jedoch eine zusätzliche Regel: Spieler, die das Labyrinth mit höherem Level reinigen, haben immer einen höheren Rang, egal wie lange die Zeitkosten sind.
Natürlich können Sie versuchen, den gepaarten Wert [T, L] mit einem Algorithmus, der den Regeln folgt, einer reellen Zahl [R] zuzuordnen und dann alle Spieler mit dem Wert [R] zu bewerten.
Wenn jedoch eine stabile Sortierung möglich ist, können Sie die gesamte Liste einfach nach [T] (zuerst schnellere Spieler) und dann nach [L] sortieren. In diesem Fall wird die relative Reihenfolge der Spieler (nach Zeitkosten) nicht geändert, nachdem Sie sie nach der Ebene des von ihnen gereinigten Labyrinths gruppiert haben.
PS: Natürlich ist der Ansatz, zweimal zu sortieren, nicht die beste Lösung für das jeweilige Problem, aber um die Frage nach dem Poster zu erklären, sollte es ausreichen.
quelle
Eine stabile Sortierung gibt immer dieselbe Lösung (Permutation) bei derselben Eingabe zurück.
Zum Beispiel wird [2,1,2] unter Verwendung einer stabilen Sortierung als Permutation [2,1,3] sortiert (zuerst ist Index 2, dann Index 1, dann Index 3 in der sortierten Ausgabe). Dies bedeutet, dass die Ausgabe immer auf die gleiche Weise gemischt wird. Andere nicht stabile, aber immer noch korrekte Permutation ist [2,3,1].
Die schnelle Sortierung ist keine stabile Sortierung, und die Permutationsunterschiede zwischen denselben Elementen hängen vom Algorithmus für die Auswahl des Pivots ab. Einige Implementierungen werden zufällig ausgewählt, und dies kann zu einer schnellen Sortierung führen, die unterschiedliche Permutationen bei derselben Eingabe mit demselben Algorithmus ergibt.
Ein stabiler Sortieralgorithmus ist deterministisch notwendig.
quelle
sort([(5,3),(1,5),(3,3),(1,3)], x) => [(1,5),(1,3),(3,3),(5,3)]. Ich kann eine deterministische Sortierung vornehmen, die immer (deterministisch) ausgibt.[(1,3),(1,5),(3,3),(5,3)]Dies ist jedoch keine stabile Sortierung.Einige weitere Beispiele für den Grund für den Wunsch nach stabilen Sorten. Datenbanken sind ein häufiges Beispiel. Nehmen Sie den Fall einer Transaktionsdatenbank, die Nachname, Vorname, Kaufzeitpunkt, Artikelnummer und Preis enthält. Angenommen, die Datenbank ist normalerweise nach Datum und Uhrzeit sortiert. Dann wird eine Abfrage durchgeführt, um eine sortierte Kopie der Datenbank nach Nachname zu erstellen, da eine stabile Sortierung die ursprüngliche Reihenfolge beibehält, obwohl der Vergleich der Anfrage nur Nachname beinhaltet, werden die Transaktionen für jeden Nachnamen durchgeführt in Datenreihenfolge sein.
Ein ähnliches Beispiel ist klassisches Excel, bei dem die Sortierung auf drei Spalten gleichzeitig beschränkt ist. Um 6 Spalten zu sortieren, wird eine Sortierung mit den niedrigstwertigen 3 Spalten durchgeführt, gefolgt von einer Sortierung mit den höchstwertigen 3 Spalten.
Ein klassisches Beispiel für eine stabile Radix-Sortierung ist ein Kartensortierer, der zum Sortieren nach einem Feld mit numerischen Spalten der Basis 10 verwendet wird. Die Karten werden von der niedrigstwertigen bis zur höchstwertigen Ziffer sortiert. Bei jedem Durchgang wird ein Kartenspiel gelesen und entsprechend der Ziffer in dieser Spalte in 10 verschiedene Fächer aufgeteilt. Dann werden die 10 Kartenfächer der Reihe nach wieder in den Eingabetrichter gelegt ("0" -Karten zuerst, "9" -Karten zuletzt). Dann wird ein weiterer Durchgang durch die nächste Spalte durchgeführt, bis alle Spalten sortiert sind. Tatsächliche Kartensortierer haben mehr als 10 Fächer, da eine Karte 12 Zonen enthält, eine Spalte leer sein kann und ein falsch gelesenes Fach vorhanden ist. Zum Sortieren von Buchstaben sind 2 Durchgänge pro Spalte erforderlich, 1. Durchgang für Ziffer, 2. Durchgang für die Zone 12 11.
Später (1937) gab es Kartensammelmaschinen, mit denen zwei Kartenspiele durch Vergleichen von Feldern zusammengeführt werden konnten. Die Eingabe bestand aus zwei bereits sortierten Kartenspielen, einem Master-Deck und einem Update-Deck. Der Collator führte die beiden Decks zu einem neuen Materialfach und einem Archivfach zusammen, das optional für Master-Duplikate verwendet wurde, sodass das neue Master-Fach nur bei Duplikaten über Aktualisierungskarten verfügt. Dies war wahrscheinlich die Grundlage für die Idee hinter der ursprünglichen Zusammenführungssorte (von unten nach oben).
quelle