20.05.2012

Selection Sort

Selection Sort (Sortieren durch Auswählen) ist ein einfacher vergleichsbasierter Sortieralgorithmus. Es ist vergleichbar mit InsertionSort und sehr intuitive zu verstehen. Leider ist es auch sehr langsam im Verleich mit den erweiterten Sortierverfahren wie MergeSort, QuickSort oder HeapSort.

sehr einfach zu verstehen und zu implementieren
sehr schnell bei kleinen Datenmengen
sehr schnell bei genügend vorsortierten Daten
stabil (die Reihenfolge von schon sortierten Elementen ändert sich nach Sortierung nicht)
in-place (bzw. in-situ, d.h. es wird kein zusätzlicher Speicher benötigt)

Idee

Das Verfahren ist relativ einfach: Die zu sortierende Folge wird in zwei Teile aufgeteilt: eine bereits sortierte Folge und die restlich noch unsortierte Folge. In jedem Iterationsschritt wird das Minimum aus der unsortierten Folge bestimmt und mit dem ersten Element dieser unsortierten Folge vertauscht. Man beginnt mit der gesamten Folge als zu sortierende Folge und ist fertig, wenn alle Elemente sich in der sortierten Folge befinden und die Folge somit komplett sortiert ist.

Damit das Verfahren stabil sortiert ist es nötig das Minimum nicht zu vertauschen sondern an die sortierte Folge anzuhängen, sodass es sich zwischen sortierter und unsortierter Folge befindet. Dies macht das Verfahren stabil, jedoch wird mehr Rechenzeit verbraucht, da Elemente im Array verschoben werden müssen.

Applet

Das Applet (benötigt Java) visualisiert einen SelectionSort auf maximal 16 Elemente. Dabei wird stets das Minimum des unsortierten Teils ermittelt und zwischen sortierten und unsortierten Teil eingefügt. Mit Insert lassen sich Werte zur Folge hinzufügen, mit Random Fill erhält man eine zufällige volle Folge generiert und mit Clear löscht man die aktuelle Folge. Mit einem Klick auf Sort wird stets ein Schritt des Verfahrens visualisiert.

Quellcode (Java)

Java Code:

Syntax Highlightning by Beautifier

public class SelectionSort { public static void selectionSort (int[] a) { //durchlaufe die Folge ... //und vertausche mit Minimum der unsortierten Folge for (int i=0; i<a.length; i++) { swap(a, i, minIndex(a, i)); } } //finde den Index des Minimum nach Position i private static int minIndex (int[] a, int i) { int m = i; //setze i as vorläufiges Minimum for (int j=i+1; j<a.length; j++) { //falls kleiner als das Minimum, dann neues Minimum if (a[j] < a[m]) m = j; } return m; } //vertauscht zwei Elemente im Array private static void swap (int[] a, int i, int j) { int h = a[i]; a[i] = a[j]; a[j] = h; } }

Varianten

HeapSort kann als eine Variante angesehen werden, denn auch hier wird das Minimum bestimmt und ausgewählt. HeapSort jedoch verwendet eine Heap Datenstruktur zur schnelleren Bestimmung des Minimum und ist somit effizienter.

Anstatt nach dem Minimum zu suchen, auch MinSort genannt, kann man auch nach dem Maximum suchen, MaxSort genannt. Verwendet man beide Verfahren Min- und MaxSort gleichzeitig, so kann man in einem Durchlauf sowohl Minimum als auch Maximum finden. Diese Variante nennt sich ShakeSort.

Analyse

SelectionSort benötigt n-1 Durchläufe um jeweils das Minimum zu bestimmen. Beim ersten Mal benötigt das Bestimmen des Minimums n-1 Vergleiche, beim zweiten Mal n-2 usw. So kann man sich die Laufzeit des Algorithmus bestimmen als
$SelectionSort Worst Case Komplexität$

Weiterführende Links und Literatur

Liste von weiteren Sortierverfahren
[1] SelectionSort bei Wikipedia (DE)
[2] SelectionSort bei Wikipedia (EN)
[3] Buch: "Algorithmen" von Robert Sedgewick
[4] Buch: "Algorithmen in Java" von Robert Sedgewick

Last Update: 05.04.2011 02:46:53