Dessa är tre enkla O(n²) jämförelsesortningar. De är långsamma på stora inmatningar men enkla att förstå och användbara för att lära sig sorteringsmekanikmens grundvalar.
Dessa är tre enkla O(n²) jämförelsesortningar. De är långsamma på stora inmatningar men enkla att förstå och användbara för att lära sig sorteringsmekanikmens grundvalar.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| Sortering | Bäst | Värst | Stabil | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nej | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |
Insertion sort är faktiskt snabb för små eller nästan sorterade arrayer och används inuti hybridsortningar. Undvik alla tre på stora osorterade data — använd istället O(n log n) sortningar.
Dessa sortningar bygger intuition för invarianter, byten och stabilitet innan du tacklar mer avancerade algoritmer.
Insertion sort förekommer särskilt inuti produktionssorteringar (som Timsort) för små subarrayer.
Att förstå varför de är O(n²) gör steget till O(n log n) sortningar meningsfullt.