Algorithmen und Datenstrukturen in C/ Insertionsort

Prinzip

Bei Insertionsort wird zunächst ein Element aus der unsortierten Folge entnommen und an der korrekten Position der sortierten Folge eingefügt. Hierbei müssen eventuell vorhandene Elemente geeignet verschoben werden.

Implementierung in C

void insertionsort(int *const data, size_t const n) {
	size_t i;
	for (i = 1; i < n; ++i) {
		int tmp = data[i];
		size_t j = i;
		while (j > 0 && tmp < data[j-1]) {
			data[j] = data[j-1];
			--j;
		}
		data[j] = tmp;
	}
}

Laufzeit-Komplexität

Die Laufzeitkomplexität für Insertionsort beträgt im Best-Case O(n), im Durchschnitt O(n²) und schlechtesten Fall ebenfalls O(n²).

Eigenschaften

Beim Insertionsort handelt es sich um einen stabilen Sortieralgorithmus, sofern die Eingabe in ihrer Reihenfolge abgearbeitet wird.

<< Shakersort | Inhaltsverzeichnis | Selectionsort >>