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.
<< Shakersort | Inhaltsverzeichnis | Selectionsort >>