Algorithmen und Datenstrukturen in C/ Insertionsort

Aus Wikibooks
Zur Navigation springen Zur Suche springen

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 Durchschnitt O(n) und schlechtesten Fall O(n²).

Eigenschaften[Bearbeiten]

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

<< Shakersort | Inhaltsverzeichnis | Selectionsort >>