Jedná se o tři jednoduché O(n²) třídící algoritmy porovnáním. Jsou pomalé na velkých vstupech, ale snadno pochopitelné a užitečné pro výuku mechaniky třídění.
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]
| Třídění | Nejlepší | Nejhorší | Stabilní | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ano | Ano |
| Selection | O(n²) | O(n²) | Ne | Ano |
| Insertion | O(n) | O(n²) | Ano | Ano |
Insertion sort je skutečně rychlý na malých nebo téměř seřazených polích a používá se v hybridních třídících algoritmech. Vyhněte se všem třem na velkých neseřazených datech — místo toho použijte O(n log n) třídění.
Tyto algoritmy budují intuici pro invarianty, výměny a stabilitu, než se pustíte do pokročilých algoritmů.
Insertion sort se zvlášť objevuje uvnitř produkčních třídících algoritmů (jako Timsort) pro malá pole.
Pochopení, proč jsou O(n²), dělá přechod na O(n log n) třídění smysluplným.