Algorithmen und Datenstrukturen in C/ Insertionsort

PrinzipBearbeiten

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 CBearbeiten

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ätBearbeiten

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

EigenschaftenBearbeiten

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