Sortieralgorithmen sind in der Informatiker-Ausbildung sehr beliebt. Wir werden in der zugehörigen Übung Arrays mit verschiedenen Sortieralgorithmen sortieren. Darunter BubbleSort und SelectionSort. Es gibt aber noch viel mehr solcher Algorithmen.

Algorithmen allgemein

Verfahren mit einer endlichen
 Beschreibung unter Verwendung wohldefinierter Einzelanweisungen.

Beachten Sie, dass die Beschreibung endlich sein muss, nicht die Laufzeit/Ausführung. Ein wohldefinierter Einzelschritt ist eindeutig beschrieben und auch tatsächlich ausführbar. Die Beschreibung muss nicht unbedingt in einer Programmiersprache festgehalten sein. Dies ist zum Beispiel auch ein Algorithmus:

 Handy in die Hand nehmen
 Nummer wählen
 Sprechen
 Auflegen

Die meisten Algorithmen sind jedoch sicherlich in Programmiersprachen festgehalten. Solche für Compiler formulierte Algorithmen nennt man Programme. Ein Programm in Ausführung nennt man Prozess. Algorithmen können verschiedene Eigenschaften besitzen.

Eigenschaften

Terminiertheit

Der Algorithmus kommt nach einer endlichen Anzahl von Schritten zu einem Ende

Determiniertheit

Die gleiche Eingabe eines Algorithmus erzeugt auch die gleiche Ausgabe

Determinisimus

Zu jedem Zeitpunkt der Ausführung muss der nächste Schritt eindeutig definiert sein

Sortieralgorithmen

Die Motivation für die Verwendung von Sortieralgorithmen in der Informatik-Ausbildung ist vielgestaltig. Ein großer Teil der weltweiten Rechenleistung fließt in das Sortieren. Kaum ein Medium stellt Informationen unsortiert dar. Ebenso ist das Suchen in Informationssystemen eine ubiquitäre Operation. In sortierten Datensätzen lässt es sich deutlich schneller suchen. Möchte ich in einem unsortieren Array der Länge n wissen, ob das Element X enthalten ist, muss ich n-Mal vergleichen. In einem sortierten Array sind weniger Vergleiche notwendig, da ich aufhören kann, weiter zu Forschen, wenn ich in der Sortierreihenfolge bei einem Wert angekommen bin, der den von Element X über-/unterschritten hat. Zudem ist das EVA-Prinzip hier wunderbar offenkundig.
Zu guter Letzt erkennt das menschliche Gehirn besonders schnell, ob Datensätze sortiert sind. Wir können also sehr schnell überprüfen, ob unser Sortieralgorithmus korrekte Ergebnisse liefert.

Implementierung im Projekt

Sehen Sie sich das folgende Video an, um im entsprechenden Projekt (Link auf der rechten Seite), den InsertionSort nachzuprogrammieren. Anschließend finden Sie weiter unten je ein Video zu SelectionSort und zu BubbleSort. Implementieren Sie diese Algorithmen ebenso im Projekt.

SelectionSort

BubbleSort

Weitere Information

Visualisierung von Sortieralgorithmen mit Volkstänzen
Visualisierung von Algorithmen durch Animationen