Algorithmen und Datenstrukturen in C/ Insertionsort
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.
<< Shakersort | Inhaltsverzeichnis | Selectionsort >>