Dette er tre enkle O(n²) sammenligningssorteringer. De er trege på store inndatamengder, men enkle å forstå og nyttige for å lære mekanikkene i sortering.
Dette er tre enkle O(n²) sammenligningssorteringer. De er trege på store inndatamengder, men enkle å forstå og nyttige for å lære mekanikkene i sortering.
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 | Best | Verste | Stabil | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nei | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |
Insertion sort er genuint raskt for små eller nesten-sorterte arrays og brukes inne i hybridsorteringer. Unngå alle tre på store usorterte data — bruk O(n log n) sorteringer i stedet.
Disse sorteringene bygger intuisjon for invarianter, bytter og stabilitet før du takler avanserte algoritmer.
Insertion sort dukker særlig opp inne i produksjonssorteringer (som Timsort) for små subarrayer.
Å vite hvorfor de er O(n²) gjør spranget til O(n log n) sorteringer meningsfullt.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner