Algorithmen und Datenstrukturen in C/ Selectionsort

Prinzip

Für Selectionsort wird das zu sortierende Feld in das zunächst leere sortierte Feld S und das unsortierte Feld U aufgeteilt. Sodann wird das kleinste Element aus U gesucht und mit dem ersten Element aus U vertauscht, bis U leer ist.

Implementierung in C

void selectionsort(int *const data, size_t const n) {
	size_t left = 0;
	while (left < n) {
		size_t min = left;
		size_t i;
		for (i = left+1; i < n; ++i) {
			if (data[i] < data[min]) {
				min = i;
			}
		}
		int tmp = data[min];
		data[min] = data[left];
		data[left++] = tmp;
	}
}

Laufzeit-Komplexität

Die Laufzeitkomplexität für Selectionsort beträgt im Durchschnitt und schlechtesten Fall O(n²).

Eigenschaften

Beim Selectionsort handelt es sich um einen instabilen Sortieralgorithmus.

<< Insertionsort | Inhaltsverzeichnis | Shellsort >>