Sortieralgorithmen

Selection Sort

Dies ist nur eine äußst kurze Zusammenfassung einiger Sortieralgorithmen. Für mehr Informationen darüber schlage ich Wikipedia oder ähnliche Quellen vor.

Prinzip

Suche für jedes Element das kleinste Element von den darauffolgenden Elementen und vertausche es mit dem aktuellen. Die Elemente werden von vorn nach hinten abgearbeitet.

Beispiel

Insert Sort

Prinzip

Der Vektor wird einmal von vorne nach hinten durchlaufen. Dabei wird jedes Element einzeln genommen und in Elemente vor ihm eingeordnet.

Beispiel

Bubble Sort

Prinzip

Der Vektor wird durchlaufen und dabei wird jedes Element mit seinem jeweiligen benachbarten Element verglichen und ggf. vertauscht. Der Vektor wird so oft durchlaufen bis richtige Reihenfolge herstellt ist.

Beispiel

Shell Sort

Prinzip

Die Elemente werden in eine k Spalten breite Matrix geschrieben und spaltenweise sortiert. Es werden mehrere Durchgänge durchgeführt, bei denen das k jeweils verringert wird.

Hinweise

1. Für das Sortieren innerhalb der Spalten muss ein anderes Sortierverfahren angewandt werden.
2. Umgesetzt auf einen Vektor werden immer die Elemente miteinander verglichen, die einen Abstand von k haben.

Beispiele

Umwandlung von einem Vektor zu einer Matrix mit 3 Spalten:

Direkt auf einen Vektor angewandt (gleiche Farben werden verglichen):

Quick Sort

Bei diesem Verfahren ist eines der beiden sehr effektiven Teile-und-Herrsche Algorithmen. Hierbei wird die hauptsächliche Arbeit im Teile-Schritt gemacht.

Prinzip

Für den Vektor wird ein Pivot-Element ausgewählt und alle anderen Elemente werden dann in zwei Vektoren aufgeteilt, je nachdem ob das jeweilige Element größer oder kleiner als das Pivot-Element ist. Dieses Prinzip wird dann rekursiv auf die beiden neuen Vektoren angewandt bis es nur noch eine Länge von eins hat.

Hinweis

Das Pivot-Element kann ein beliebiges Element sein. Es empfiehlt sich ein einfaches wie das erste oder letzte Element des Vektors.

Beispiel

Kommentare