Insertion-Sort
- einfach, stabil
- effizient bei kleinen oder vorsortierten Datenmengen
- vgl. Spielkarten sortieren
- Laufzeitkomplexität:
- Best: O(n)
- Average: O(n²)
- Worst: O(n²)
Pseudocode
Funktion InsertionSort(array)
FOR i := 1 bis Länge(array) DO
temp := array[i]
j := i - 1
WHILE j >= 0 und array[j] > temp DO
array[j + 1] := array[j]
j := j - 1
array[j+1] = temp
Ergebnis := array
- Python
- C#
def insertion_sort(array)
for i in range(1,len(array)):
temp = array[i]
j = i - 1
while (j >= 0 and array[j] > temp):
array[j + 1] = array[j]
j -= 1
array[j+1] = temp
return array
static void InsertionSort(int[] array)
{
int temp;
for (int i = 1; i < array.Length; i++)
{
temp = array[i];
int j = i - 1;
while (j >= 0 && array[j] > temp)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}