WikiDer > Sortieralgorithmus

Sorteeralgoritme

EIN Sortieralgorithmus ist ein Algorithmus zu Elementen von a aufführen um sie in eine bestimmte Reihenfolge zu bringen. In der Geschichte der Computerprogrammierung Für diese Aufgabe wurden viele Algorithmen entwickelt, die sich durch unterschiedliche Geschwindigkeit, Speichernutzung und Verhalten bei steigender Anzahl zu sortierender Elemente auszeichnen. Zum Beispiel eine Packung sortieren Kartenspielen hat andere Anforderungen als das Sortieren der Telefonbuch von New York.

Das Studium von Sortieralgorithmen ist eine Möglichkeit, viele Aspekte der Computernutzung in vielen Informatikkursen zu erklären. Sortieralgorithmen gelten auch für Datenkompression und Speicherverwaltung.

Donald Knuth hat in seinem klassischen Werk Die Kunst der Computerprogrammierung ein wichtiger Teil der Sortierung und Suchalgorithmen gewidmet.[1]

Eigenschaften

Zu den Eigenschaften, in denen sich Sortieralgorithmen unterscheiden, gehören:

  • Einfachheit der Methode;
  • Geschwindigkeit des Verfahrens und Ausmaß, in dem es mit zunehmendem Sortierproblem abnimmt (mehr zu sortierende Elemente);
  • Speichernutzung;
  • Verwendung von nicht zufällig gelesenem Peripheriespeicher (z. B. Bänder oder Disketten)
  • pathologische Fälle (schlimmsten Fall) bei denen sich der Algorithmus plötzlich viel schlechter als gewöhnlich verhält (zum Beispiel wenn die Liste bereits sortiert ist oder wenn die Liste genau in umgekehrter Reihenfolge sortiert wird);
  • Stabilität, wobei Elemente, die gleich sind, in der gleichen Reihenfolge gehalten werden. Dies ist wichtig, wenn Sie nach verschiedenen Merkmalen nacheinander sortieren möchten.

Algorithmen

Einige Algorithmen sind:

  • Bogosort (ebenfalls dumme sorte oder langsam sortieren) wurde scherzhaft als der theoretisch schlechteste Sortieralgorithmus vorgeschlagen.
  • Blasensortierung: das Komplexitätsgrad von Blase sortieren ist nein2, was es für lange Listen sehr ineffizient macht, es sei denn, die Elemente versehentlich sind fast in ordnung. Blasensortierung ist sehr leicht zu verstehen.
  • Zählen sortieren: Ein effizienter Sortieralgorithmus, der nur für ganze Zahlen in einem begrenzten Bereich geeignet ist.
  • Hashsort. Der Komplexitätsgrad von hashsort ist n. Das macht hashsort zum schnellstmöglichen Sortieralgorithmus für kleine Serien (für große Serien ist ein logarithmischer Komplexitätsgrad schneller (wegen asymptotischem Verhalten)). Die Speichernutzung ist jedoch nicht immer von Vorteil und funktioniert auch schlecht für Listen, die aus vielen gleichen Elementen bestehen. Darüber hinaus ist es nicht sicher, dass die verbleibende sortierte Reihenfolge keine leeren Elemente enthält, und es muss ein Weg gefunden werden, Elemente zu unterscheiden, die zu demselben Hashkey führen.
Ungerade Sortierung
Ungerade Sortierung
  • Haufen sortieren
  • Sortieren durch Einfügen
  • Zusammenführen, sortieren arbeitet, indem verschiedene Listen der Reihe nach abgearbeitet werden, und ist daher besonders geeignet, wenn die zu sortierende Datenmenge viel größer ist, als im Computerspeicher gespeichert werden kann (früher wurden Bänder verwendet, die nie vollständig in den Speicher passen). Außerdem ist die Methode stabil (vorausgesetzt, sie ist richtig geschrieben).
  • Ungerade Sortierung
  • Pfannkuchen sortieren
  • Schnelle Sorte. Der Komplexitätsgrad von schnelle Sorte ist n log n. In vielen Fällen ist dies die effizienteste bekannte Methode für große Listen. Die Methode ist leicht zu erklären, aber es ist nicht sofort intuitiv klar, warum sie so gut funktioniert. Er hat auch ein sehr schlechtes schlimmsten Fall (keine2), die jedoch durch einen kleinen Eingriff (z.B. willkürliche Wahl des Kipppunktes) leicht überwunden werden kann. In normalen Situationen kommt dieser schlimmsten Fall auch nicht für.
  • Radix sortieren
  • Auswahl sortieren
  • Muschelsortierung
  • Direktauswahl sortieren

Viele Sortierroutinen in Programmierbibliotheken bestehen aus einer Reihe von Algorithmen, die dort eingesetzt werden, wo sie stark sind. Beispielsweise, schnelle Sorte für lange Listen gut kombinierbar mit gerade auswahl sortieren für kurze Listen.

Verweise

  1. ↑Donald E. Knuth, Die Kunst der Computerprogrammierung, Band 3: Sortieren und Suchen. Zweite Auflage (Reading, Massachusetts: Addison-Wesley, 1998), xiv 780 S. ausklappen. ISBN 0-201-89685-0

Externe Links

Siehe die Kategorie Sortieralgorithmen von Wikimedia Commons für Mediendateien zu diesem Thema.