Acestea sunt trei sortări simple de comparație O(n²). Sunt lente pe intrări mari, dar ușor de înțeles și utile pentru predarea mecanicii sortării.
Acestea sunt trei sortări simple de comparație O(n²). Sunt lente pe intrări mari, dar ușor de înțeles și utile pentru predarea mecanicii sortării.
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]
| Sort | Cel mai bun | Cel mai rău | Stabil | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Da | Da |
| Selection | O(n²) | O(n²) | Nu | Da |
| Insertion | O(n) | O(n²) | Da | Da |
Insertion sort este cu adevărat rapid pentru tablouri mici sau aproape sortate și este folosit în sortări hibride. Evitați toți trei pe date mari nesortate — folosiți în schimb sortări O(n log n).
Aceste sortări construiesc intuiție pentru invarianți, schimburi și stabilitate înainte de a aborda algoritmi avansați.
Insertion sort în special apare în sortări din producție (cum ar fi Timsort) pentru submatrice minuscule.
Cunoscerea motivului pentru care sunt O(n²) face salt către sortări O(n log n) semnificativ.
O bibliotecă de întrebări de interviu IT cu răspunsuri detaliate — de la Junior la Senior.
Donează