Zum Inhalt springen

Algorithmen und Datenstrukturen in C/ Insertionsort

Aus Wikibooks

Prinzip

[Bearbeiten]

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

[Bearbeiten]
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

[Bearbeiten]

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

Eigenschaften

[Bearbeiten]

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