Stabilität in Sortieralgorithmen - Eine Behandlung der Gleichheit

Algorithmen sind das Herzstück der Informatik. Zum Sortieren verwendete Algorithmen gehören zu den grundlegendsten, nützlichsten und folglich allgegenwärtigsten.

Algorithmus - eine endliche Menge eindeutiger Schritte zur Lösung eines bestimmten Problems.

Wir sortieren ständig und oft unbewusst und verlassen uns auf die Reihenfolge der gruppierten Objekte. Zum Beispiel ordnen wir Aufgaben auf einer Liste nach Priorität. Wir stapeln Bücher in Regalen nach ihrer Höhe. Wir sortieren Zeilen in einer Tabelle oder Datenbank oder verlassen uns auf die alphabetische Reihenfolge der Wörter in einem Wörterbuch. Manchmal nehmen wir in geordneten Arrangements sogar eine bestimmte Art von Schönheit wahr.

Als Programmierer ist es wichtig zu wissen, wie wir sortieren, da dies Auswirkungen darauf hat, wie eine sortierte Anordnung aussehen könnte. Nicht alle Sorten bestellen Objekte auf die gleiche Weise! Aus diesem Grund unterscheiden sich die Ergebnisse der Sortiervorgänge je nach den verwendeten Algorithmen. Wenn dies nicht bestätigt wird, können wir uns selbst oder die Personen, die unsere Software verwenden, überraschen.

Die Stabilität von Sortieralgorithmen ist eine der unterscheidenden Eigenschaften unter ihnen. Es geht darum, wie der Algorithmus vergleichbare Elemente mit gleichen Sortierschlüsseln behandelt.

Sortierschlüssel - Ein Schlüssel, mit dem die Reihenfolge der Elemente in einer Sammlung bestimmt wird, z. B. Alter, Größe, Position im Alphabet usw.

Ein stabiler Sortieralgorithmus behält die relative Reihenfolge der Elemente mit gleichen Sortierschlüsseln bei. Ein instabiler Sortieralgorithmus funktioniert nicht. Mit anderen Worten, wenn eine Sammlung mit einem stabilen Sortieralgorithmus sortiert wird, behalten Elemente mit denselben Sortierschlüsseln ihre Reihenfolge bei, nachdem die Sammlung sortiert wurde.

Ein Beispiel, Code und eine Demo

Das obige Bild zeigt den Effekt einer stabilen Sortierung. Links wurden die Daten alphabetisch nach Namen sortiert. Nachdem Sie die Daten nach Note sortiert haben, können Sie sehen, dass die alphabetische Reihenfolge der Namen für jede Zeile mit derselben Note beibehalten wurde.

Bei einer instabilen Sortierung gibt es keine Garantie dafür, dass die alphabetische Reihenfolge wie im obigen Bild gezeigt beibehalten wird.

Sie brauchen nicht immer eine stabile Sorte

Es ist besonders wichtig zu wissen, ob die von Ihnen verwendete Sorte stabil ist oder nicht. Insbesondere in Situationen, in denen Ihre Daten bereits eine Reihenfolge haben, die Sie beibehalten möchten, wenn Sie sie nach einem anderen Sortierschlüssel sortieren. Sie haben beispielsweise Zeilen in einer Tabelle mit Schülerdaten, die standardmäßig nach Namen sortiert sind. Sie möchten es auch nach Noten sortieren, während Sie die sortierte Reihenfolge der Namen beibehalten.

Andererseits spielt die Stabilität der Sortierung keine Rolle, wenn die Sortierschlüssel der Objekte in einer Sammlung die Objekte selbst sind - beispielsweise ein Array von Ganzzahlen oder Zeichenfolgen -, da wir den Unterschied zwischen den duplizierten Objekten nicht erkennen können Schlüssel.

// JavaScript
// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.
var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]
// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.
var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

Sorten sind überall - kennen Sie Ihre Sorten

Es ist ziemlich einfach herauszufinden, ob die Standardsortierung in Ihrer Programmiersprache oder Bibliothek stabil ist. Die Dokumentation sollte diese Informationen enthalten. Zum Beispiel ist die Standardsortierung in Python stabil, in Ruby instabil und undefiniert? in JavaScript (dies hängt von der Implementierung des Browsers ab).

Hier sind einige gängige Sortieralgorithmen und ihre Stabilität:

  • Einfügungssortierung - Stabil
  • Auswahlsortierung - Instabil
  • Blasensortierung - Stabil
  • Sortierung zusammenführen - Stabil
  • Shell Sort - Instabil
  • Timsort - Stabil

Eine ausführlichere Liste finden Sie in Wikipedia.

Es ist Demo-Zeit? ‍?

Diese Demo zeigt den Effekt der Verwendung eines stabilen (Einfügesortierung) und instabilen Sortieralgorithmus (Auswahlsortierung) zum Sortieren einer kleinen Datentabelle. Ich hatte ein bisschen Spaß und habe React praktisch rückentwickelt, während ich das gebaut habe. Schauen Sie sich die Quelle an.

Was kommt als nächstes?

Wenn Sie mehr über die Stabilität anderer Sortieralgorithmen erfahren möchten, bietet Wikipedia eine gute Vergleichstabelle und zusätzliche Informationen zu bekannten Sortieralgorithmen.

Bis zum nächsten Mal Frieden.

Etwas Neues gelernt oder diesen Artikel gerne gelesen? Klatschen Sie es?, Teilen Sie es, damit auch andere lesen können, und folgen Sie ihm, um mehr zu erfahren. Fühlen Sie sich frei, auch einen Kommentar zu hinterlassen.