Datenstruktur - Sortiertechniken
Sortieren bezieht sich auf das Anordnen von Daten in einem bestimmten Format. Der Sortieralgorithmus gibt an, wie Daten in einer bestimmten Reihenfolge angeordnet werden sollen. Die meisten gängigen Ordnungen erfolgen in numerischer oder lexikografischer Reihenfolge.
Die Bedeutung der Sortierung liegt in der Tatsache, dass die Datensuche auf einem sehr hohen Niveau optimiert werden kann, wenn Daten sortiert gespeichert werden. Die Sortierung wird auch verwendet, um Daten in besser lesbaren Formaten darzustellen. Im Folgenden finden Sie einige Beispiele für das Sortieren in realen Szenarien:
Telephone Directory - Das Telefonverzeichnis speichert die Telefonnummern von Personen, die nach ihren Namen sortiert sind, so dass die Namen leicht gesucht werden können.
Dictionary - Das Wörterbuch speichert Wörter in alphabetischer Reihenfolge, so dass die Suche nach Wörtern einfach wird.
In-Place-Sortierung und Nicht-In-Place-Sortierung
Sortieralgorithmen erfordern möglicherweise zusätzlichen Platz zum Vergleichen und temporären Speichern weniger Datenelemente. Diese Algorithmen benötigen keinen zusätzlichen Speicherplatz, und die Sortierung soll direkt oder beispielsweise innerhalb des Arrays selbst erfolgen. Das nennt manin-place sorting. Die Blasensortierung ist ein Beispiel für die In-Place-Sortierung.
Bei einigen Sortieralgorithmen benötigt das Programm jedoch Speicherplatz, der größer oder gleich den zu sortierenden Elementen ist. Eine Sortierung, die gleich viel oder mehr Platz benötigt, wird aufgerufennot-in-place sorting. Die Zusammenführungssortierung ist ein Beispiel für eine nicht vorhandene Sortierung.
Stabile und nicht stabile Sortierung
Wenn ein Sortieralgorithmus nach dem Sortieren des Inhalts die Reihenfolge ähnlicher Inhalte, in denen sie angezeigt werden, nicht ändert, wird er aufgerufen stable sorting.
Wenn ein Sortieralgorithmus nach dem Sortieren des Inhalts die Reihenfolge ähnlicher Inhalte ändert, in der sie angezeigt werden, wird er aufgerufen unstable sorting.
Die Stabilität eines Algorithmus ist wichtig, wenn wir die Reihenfolge der ursprünglichen Elemente beibehalten möchten, wie beispielsweise in einem Tupel.
Adaptiver und nicht adaptiver Sortieralgorithmus
Ein Sortieralgorithmus wird als adaptiv bezeichnet, wenn er bereits 'sortierte' Elemente in der Liste nutzt, die sortiert werden sollen. Das heißt, während beim Sortieren, wenn in der Quellliste bereits ein Element sortiert ist, berücksichtigen adaptive Algorithmen dies und versuchen, diese nicht neu zu ordnen.
Ein nicht adaptiver Algorithmus ist ein Algorithmus, der die bereits sortierten Elemente nicht berücksichtigt. Sie versuchen, jedes einzelne Element neu zu ordnen, um ihre Sortierung zu bestätigen.
Wichtige Begriffe
Einige Begriffe werden im Allgemeinen bei der Erörterung von Sortiertechniken geprägt. Hier finden Sie eine kurze Einführung in diese Begriffe.
Zunehmende Ordnung
Eine Folge von Werten soll in sein increasing order, wenn das aufeinanderfolgende Element größer als das vorherige ist. Zum Beispiel sind 1, 3, 4, 6, 8, 9 in aufsteigender Reihenfolge, da jedes nächste Element größer als das vorherige Element ist.
In absteigender Folge
Eine Folge von Werten soll in sein decreasing order, wenn das aufeinanderfolgende Element kleiner als das aktuelle ist. Zum Beispiel sind 9, 8, 6, 4, 3, 1 in absteigender Reihenfolge, da jedes nächste Element kleiner als das vorherige Element ist.
Nicht zunehmende Reihenfolge
Eine Folge von Werten soll in sein non-increasing order, wenn das aufeinanderfolgende Element kleiner oder gleich dem vorherigen Element in der Sequenz ist. Diese Reihenfolge tritt auf, wenn die Sequenz doppelte Werte enthält. Zum Beispiel sind 9, 8, 6, 3, 3, 1 in nicht aufsteigender Reihenfolge, da jedes nächste Element kleiner oder gleich (im Fall von 3), aber nicht größer als jedes vorherige Element ist.
Nicht abnehmende Reihenfolge
Eine Folge von Werten soll in sein non-decreasing order, wenn das aufeinanderfolgende Element größer oder gleich seinem vorherigen Element in der Sequenz ist. Diese Reihenfolge tritt auf, wenn die Sequenz doppelte Werte enthält. Zum Beispiel sind 1, 3, 3, 6, 8, 9 in nicht abnehmender Reihenfolge, da jedes nächste Element größer oder gleich (im Fall von 3), aber nicht kleiner als das vorherige ist.