Quadratische Suchalgorithmen

Die simpelsten Sortieralgorithmen haben eine quadratische Laufzeit. Ist die Datenmenge beispielsweise doppelt so groß, so vervierfacht sich (im schlechtesten Fall) die Ausführungsdauer.

Selection Sort

Das wohl intuitivste Verfahren zur Sortierung von Reihungen ist das Sortieren durch Auswahl.

Wie der Namen schon erahnen lässt, bestimmt der Algorithmus denjenigen Index, an welchem sich das kleinste Element – das Element mit minimalem Schlüssel – befindet. Ist dieses Element gefunden, so wird es mit dem ersten Element (Element mit Index $1$) vertauscht. Im Array wird also das kleinste Element ausgewählt und an die erste Stelle gesetzt.

Anschließend sucht der Algorithmus das Element mit dem zweitkleinsten Schlüssel und vertauscht es mit dem zweiten Element der Liste. Hierbei sucht der Algorithmus nicht direkt nach dem zweitkleinsten Element. Vielmehr durchsucht er die Reihung ab der zweiten Position nach dem kleinsten Element.

Die dynamisch-interaktive Visualisierung am Ende der Seite zeigt dieses Verfahren.

Bubble Sort

Ein ähnlich einfaches Sortierverfahren ist der Bubble Sort. Die Vorstellung ist, dass die Elemente in einem Stapel wie Blasen nach oben steigen, bis sie am richtigen Platz sind.

Das zu sortierende Feld wird von links nach rechts durchlaufen. Dabei werden zwei benachbarte Elemente vertauscht, wenn das größere vorne ist. Aufgrund dieser geschachtelten Schleife werden ebenfalls $n^2$ Vergleiche benötigt.

Die dynamisch-interaktive Visualisierung am Ende der Seite zeigt dieses Verfahren.

Shaker Sort

Eine Abwandlung des Bubble Sort ist der Shaker Sort. Die Wahrscheinlichkeit einer großen Laufzeit ist gegenüber dem Bubble Sort geringer und somit ist dieses Verfahren in der Praxis vorzuziehen.

Im Gegensatz zum Bubble Sort wird hier das zu sortierende Feld abwechselnd nach oben und nach unten durchlaufen. Dabei werden die benachbarten Elemente miteinander verglichen und gegebenenfalls vertauscht.

Insert Search

Der Insert Search entnimmt der unsortierten Folge ein Element und fügt es an richtiger Stelle ein. Dabei wird das erste Element erst einmal an seiner Stelle gelassen. Wird ein Element eingefügt, werden dafür alle bisher sortierten größeren Elemente nach rechts verschoben.

In nachfolgender dynamisch-interaktiver Visualisierung kann dieser Algorithmus mit den anderen verglichen werden. Zudem ist auch schon der Quick-Sort-Algorithmus des nächsten Abschnitts auswählbar.

Anleitung: Über die Knöpfe den Suchalgorithmus auswählen und Anzahl und Startreihenfolge der zu sortierenden Liste wählen.

Mehr Informationen zu Algorithmen finden Sie unter (Dieker & Güting, 2018).