Effiziente Sortier- und Suchalgorithmen im Überblick

Verschiedene Sortieralgorithmen und ihre Effizienz

Verschiedene Sortieralgorithmen unterscheiden sich in ihrer Effizienz. Ein effizienter Algorithmus wird schneller sein und weniger Ressourcen (Speicher) verbrauchen. Die Auftragsdaten können in Massenspeichern oder im Hauptspeicher gelagert werden. Wenn die Daten in Listen gespeichert sind und in kleinen Mengen vorliegen, werden Datensätze in der Regel in Arrays zwischengespeichert. Die Verwaltung dieser Daten ist ausschließlich für intern gespeicherte Daten und massive Behandlungen vorgesehen.

Es gibt zwei grundlegende Management-Techniken im Datenmanagement: Listenverwaltung und Dateimanagement. Es werden Methoden der Organisation als interne oder externe Sortierung bezeichnet, abhängig davon, ob die zu ordnenden Artikel im Hauptspeicher (MP) oder im Sekundärspeicher (M. sekundär) liegen.

1.1. Bubble Sort

Bubble Sort ist die am wenigsten effiziente Methode. Die „Blase“ lässt allmählich kleinere Werte nach oben (up) an die Spitze des Feldes steigen, während höhere Werte im Array auf den Boden sinken. Dieser Vorgang benötigt n-1 Durchgänge. In jedem Durchgang werden Elemente gegenüber benachbarten Elementen (Paaren) verglichen und ihre Werte ausgetauscht, wenn das erste Element größer als das zweite ist. Am Ende jedes Durchlaufs „perlt“ das größte Element an den Schwanz der Unterliste. Zum Beispiel ist nach dem letzten Durchlauf das Element am Ende der Liste V[n-1] sortiert, während der vordere Teil der Liste ungeordnet bleibt.

1.2. Exchange Sort

Exchange Sort ist der einfachste Sortieralgorithmus. Er sortiert die Elemente einer Liste oder eines Vektors in aufsteigender Reihenfolge. Der Algorithmus vergleicht das Element am Ende der Liste mit den anderen und führt einen Positionstausch durch, wenn die Reihenfolge aus dem Vergleich nicht korrekt ist.

1.3. Insertion Sort

Beim Insertion Sort wird das Array zur Ordnung in zwei Teile geteilt: einen geordneten und einen ungeordneten Teil. Man nimmt das erste Element der ungeordneten Menge und fügt es an den ihm gebührenden Platz innerhalb des bereits sortierten Teils ein. Der Prozess beginnt mit der Betrachtung des ersten Elements als sortiert und setzt die Ordnung des zweiten Elements relativ zum ersten fort; das heißt, es bewegt sich entweder vorwärts oder bleibt, wo es ist. Nachdem der Index erweitert wurde, wird das erste „Nicht-Priester-geweihte“ (unsortierte) Element gekennzeichnet. Das dritte Element wird entnommen und an den passenden Platz zu den beiden vorangegangenen gesetzt. Der Index wird fortgeschritten und der Prozess wiederholt, bis alle Elemente an der richtigen Stelle sind, wodurch das Array gemäß den Spezifikationen sortiert wird.

1.4. Shell Sort

Shell Sort vergleicht im Gegensatz zur Bubble-Methode nicht zusammenhängende Elemente, die durch einen bestimmten Abstand getrennt sind. Wenn Elemente nicht in Ordnung sind, werden sie ausgetauscht. Der Algorithmus beginnt mit der Angabe einer Bandbreite oder eines großen Sprungs, vergleicht die durch dieses Intervall getrennten Elemente und tauscht sie bei Bedarf aus. Die Palette beginnt in der Regel als die Hälfte der gesamten Zeitspanne zwischen dem ersten und dem letzten Element, d. h. die Mitte ist die erste Referenz.

1.5. Quicksort

Quicksort, erfunden von C. Hoare, gilt als der beste derzeit verfügbare Sortieralgorithmus. Das Management basiert auf der Methode des Austauschs. Es besteht darin, ein Element aus einer Liste auszuwählen und dann alle anderen Elemente in Unterverzeichnissen neu anzuordnen. Dabei werden alle Elemente, die kleiner als der gewählte Punkt sind, in eine Unterliste gesetzt, und alle Elemente, die größer als das gegebene Element sind, in eine zweite Liste.

Suchalgorithmen: Sequentiell und Binär

2.1. Sequentielle Suche

Die sequentielle Suche findet ein Element in einer Liste oder einem Vektor mithilfe eines Wertes, der als „Schlüsselrolle“ fungiert. Die Vektorelemente werden nacheinander untersucht. Der Algorithmus vergleicht jedes Element des Vektors mit dem Suchbegriff. Da der Vektor nicht sortiert ist, muss das Programm im Durchschnitt den Suchbegriff mit der Hälfte der Elemente des Arrays vergleichen.

2.2. Binäre Suche

Die binäre Suche nutzt aus, dass die gespeicherten Daten bereits sortiert sind. Sie vergleicht Elemente des Arrays mit dem Suchbegriff. Dabei wird in der Mitte der Liste angesetzt, um zu prüfen, ob unser Schlüssel dem Wert des zentralen Elements entspricht. Wenn der Wert nicht der Schlüssel ist, liegt er entweder in der unteren oder der oberen Hälfte der Liste.

2.3. Suche im binären Baum

Bei der binären Suche im binären Baum kann die Suche nach einem Wert effizient durchgeführt werden, wenn der Baum geordnet ist. Dies geschieht durch Eliminierung: Wenn ein Knoten untersucht wird, können die Teilbäume ausgeschlossen werden, die den gewünschten Wert nicht enthalten können (entweder alle Werte unterhalb oder alle oberhalb). Anschließend wird die Wurzel des gewählten Teilbaums diskutiert und erneut einer der Teilbäume entfernt. Der Prozess endet, wenn der gesuchte Knoten gefunden wurde oder wenn ein Blatt des Baumes erreicht wird und keine weiteren Treffer möglich sind. Das folgende Beispiel setzt die Suche mithilfe von Rekursion um.