Inhalt
Das Bestellen einer Reihe von Elementen in einer Liste ist eine häufige Aufgabe bei der Programmierung. Oft kann ein Mensch diese Aufgabe intuitiv ausführen. Ein Computerprogramm muss jedoch eine genaue Folge von Anweisungen befolgen, um es zu vervollständigen, und diese Folge wird als Algorithmus bezeichnet. Ein Bestellalgorithmus ist eine Methode, mit der eine Liste unorganisierter Elemente in einer bestimmten Reihenfolge platziert wird. Die Reihenfolge wird durch einen Schlüssel bestimmt. Es gibt verschiedene Sortieralgorithmen, die sich in Bezug auf Effizienz und Leistung unterscheiden. Einige bekannte und wichtige dieser Art sind: Blasensortierung, Auswahlsortierung, Einfügesortierung und schnelle Sortierung.
Blasensorte
Die Blasensortierung tauscht wiederholt benachbarte Elemente aus, die nicht in Ordnung sind, bis die gesamte Liste der Elemente der Reihe nach angezeigt wird. Auf diese Weise schweben die Elemente entsprechend ihren Werten in der Liste, wobei das größte (bei aufsteigender Sortierung) am Ende jeder Iteration bis zum Ende geht.
Der Hauptvorteil dieses Algorithmus besteht darin, dass seine Implementierung einfach und bekannt ist. Darüber hinaus werden bei der Blasensortierung die Elemente ohne Verwendung von temporärem Speicherplatz geändert, wodurch der Platzbedarf minimal wird. Der Hauptnachteil ist die Tatsache, dass es keine guten Ergebnisse zeigt, wenn die Liste viele Elemente enthält. Dies liegt daran, dass diese Art der Sortierung n² Verarbeitungsschritte für jede n Anzahl von Elementen erfordert, die sortiert werden sollen. Daher ist die Blasensorte für die akademische Ausbildung geeignet, jedoch nicht für reale Anwendungen.
Auswahl sortieren
Die Auswahlsortierung durchsucht wiederholt die Liste der Elemente, wählt jeweils ein Element aus und platziert es an der richtigen Position in der Sequenz.
Der Hauptvorteil der Auswahlsortierung besteht darin, dass sie auf einer kurzen Liste gut funktioniert. Da es sich um einen Ortsbestellungsalgorithmus handelt, muss er nicht temporär gespeichert werden, außer zum Speichern der ursprünglichen Liste. Der Hauptnachteil ist die geringe Effizienz bei großen Listen. Wie bei der Blasensortierung sind für jedes n Element n² Schritte erforderlich. Darüber hinaus wird die Leistung leicht durch die anfängliche Reihenfolge der Artikel vor dem Sortiervorgang beeinflusst. Aus diesem Grund eignet sich dieser Auswahltyp nur für eine Liste, in der nur wenige Elemente in zufälliger Reihenfolge vorliegen.
Sortieren durch Einfügen
Die Einfügesortierung durchsucht die Liste wiederholt und fügt jedes Mal ein Element aus der ungeordneten Sequenz an der richtigen Position ein.
Der Hauptvorteil des Sortierens nach Einfügen ist seine Einfachheit und die gute Leistung in kleinen Listen. Da es sich um einen Platzierungsalgorithmus handelt, ist der Platzbedarf minimal. Der Nachteil ist, dass es nicht so gut funktioniert wie andere Sortieralgorithmen. Mit n² Schritten, die zum Arbeiten benötigt werden, funktioniert die Einfügesortierung auch bei großen Listen nicht gut. Es ist jedoch besonders nützlich bei Listen mit wenigen Elementen.
Schnelle Sorte
Die schnelle Sortierung basiert auf dem Prinzip der Teilung und Eroberung. Zunächst wird die Artikelliste basierend auf einem Pivot-Element in zwei Unterlisten unterteilt. Alle Elemente in der ersten Unterliste sind so angeordnet, dass sie kleiner als der Drehpunkt sind, während alle Elemente in der zweiten Unterliste so angeordnet sind, dass sie größer als der Drehpunkt sind. Der gleiche Partitionierungs- und Organisationsprozess wird wiederholt für die resultierenden Unterlisten ausgeführt, bis die gesamte Liste organisiert ist.
Die schnelle Sortierung wird von einigen aufgrund ihres erheblichen Effizienzvorteils als der beste Sortieralgorithmus angesehen, da sie mit einer großen Liste von Elementen gut funktioniert. Durch die Bestellung vor Ort wird auch kein zusätzlicher Speicherplatz benötigt. Der geringfügige Nachteil besteht darin, dass die schlechteste Leistung der durchschnittlichen Leistung der anderen oben beschriebenen Algorithmen ähnlich ist. Es ist jedoch wichtig zu beachten, dass dieser schlimmste Fall sehr selten ist. Im Allgemeinen ist die schnelle Sortierung die effizienteste und am weitesten verbreitete Methode zum Organisieren einer Liste beliebiger Größe.
