Einfache Sortierverfahren

Bei der Bearbeitung der Einstiegsaufgabe werden Sie vermutlich festgestellt haben, dass das Sortieren gar nicht so einfach ist, wenn man systematisch vorgehen möchte und sich dabei auf Möglichkeiten eines Computers beschränken muss. Dennoch haben Informatiker inzwischen eine Vielzahl an Sortierverfahren entwickelt, die alle unterschiedliche Vor- und Nachteile mit sich bringen. Wir möchten im Folgenden zunächst zwei bekannte Verfahren genauer betrachten – vielleicht befindet sich darunter auch die von Ihnen in der Erkundung 1 entwickelte Strategie:

• Sortieren durch Einfügen (Insertion Sort)
• Sortieren durch Auswählen (Selection Sort)

Bei den einfachen Sortierverfahren hat man in der Regel einen sortierten und einen unsortierten Bereich. Die Grundidee aller Verfahren besteht darin, den sortierten Bereich immer weiter zu vergrößern, so dass schließlich alle Elemente sortiert sind.

Sortieren durch Einfügen (Insertion Sort)

Bei diesem Verfahren wird das erste Element (gelb) des noch nicht sortierten Bereichs (rot) genommen und zwischengespeichert. Der bereits sortierte Bereich (grün) wird nun von rechts nach links durchlaufen, um die passende Einfügestelle für dieses Element zu suchen.

Alle Element, die größer sind als das einzufügende Element, rücken dabei um ein Feld nach rechts auf. Anschließend kann das zwischengespeicherte Element an der nun freigewordenen Einfügestelle eingefügt werden. Dieser Schritt wird solange wiederholt, bis sich alle Elemente im sortierten Bereich befinden.

Beispiel:

Zu Beginn ist das erste Element für sich betrachtet ist automatisch sortiert.

1. Durchlauf: 2 wird in den sortierten Bereich eingefügt. Da 2 kleiner ist als 6, wird die 2 vor der 6 eingefügt.

2. Durchlauf: Die 11 wird in den sortierten Bereich eingefügt. Da 11 größer ist als 6, ist ein Aufrücken nicht erforderlich. 11 wird am Ende des sortierten Bereiches eingefügt und behält somit seine Position.

3. Durchlauf: Die 7 wird in den sortierten Bereich eingefügt. Da die Einfügestelle zwischen den Elementen 6 und 11 liegt, rückt die 11 nach rechts auf und die 7 wird an der freigewordenen Stelle eingefügt.

4. Durchlauf: Die 1 wird in den sortierten Bereich eingefügt. Da alle bereits enthaltenen Elemente größer sind als die 1, rücken sie der Reihe nach um ein Feld nach rechts auf. Die 1 wird danach ganz vorne eingefügt. Usw.

Pseudocode für das Sortieren auf einem Array

Wir betrachten nun den allgemeinen Fall, nämlich ein Array A mit n Elementen:

Das Sortieren durch Einfügen auf diesem Array wird dann durch folgenden Pseudecode beschrieben:

Aufwand

Während für den Zugriff auf das erste Element des unsortierten Bereichs stets nur ein Zugriff erforderlich ist, muss der sortierte Bereich in jedem Durchlauf bis zur Einfügestelle durchlaufen werden. Im ungünstigsten Fall, einer zuvor umgekehrten Reihenfolge, muss der sortierte Bereich jedes Mal bis zum Anfang durchlaufen werden. Als Gesamtaufwand ergibt sich dann für n zu sortierende Elemente entsprechend:

Da für das Wachstum bei großen Werten von n der Faktor n² ausschlaggebend ist, spricht man von einem quadratischen Aufwand. Es lässt sich zeigen, dass der Aufwand nicht nur im ungünstigsten Fall quadratisch ist, sondern auch im durchschnittlichen Fall.

Sortieren durch Auswählen (Selection Sort)

Beim Sortieren durch Auswählen besteht das Grundprinzip darin, das zunächst der noch nicht sortierte Bereich (rot) von links nach rechts durchlaufen wird, um das kleinste, noch nicht sortierte Element zu ermitteln. Dabei wird zu jeder Zeit die Position des aktuell kleinsten gefundenen Elements in einer Hilfsvariablen zwischengespeichert.

Nachdem der noch nicht sortierte Bereich vollständig durchlaufen wurde, wird das kleinste noch nicht sortierte Element (dessen Position in der Hilfsvariablen gespeichert ist) mit dem ersten Element des noch nicht sortieren Bereiches getauscht. Der sortierte Bereich (grün) wird dadurch um ein Element vergrößert.

Das Sortieren durch Auswählen auf dem Array wird dann durch folgenden Pseudecode beschrieben:

Download eines BlueJ-Projekts SortierDemo (Java), bei dem der Pseudocode zeilenweise in Java übersetzt ist.