To są trzy proste sortowania porównujące o złożoności O(n²). Są wolne dla dużych danych wejściowych, ale łatwe do zrozumienia i przydatne do nauczania mechaniki sortowania.
To są trzy proste sortowania porównujące o złożoności O(n²). Są wolne dla dużych danych wejściowych, ale łatwe do zrozumienia i przydatne do nauczania mechaniki sortowania.
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]
| Sortowanie | Najlepszy | Najgorszy | Stabilne | In-place |
|---|---|---|---|---|
| Bąbelkowe | O(n) | O(n²) | Tak | Tak |
| Przez wybór | O(n²) | O(n²) | Nie | Tak |
| Przez wstawianie | O(n) | O(n²) | Tak | Tak |
Sortowanie przez wstawianie jest naprawdę szybkie dla małych lub niemal posortowanych tablic i jest używane wewnątrz sortowań hybrydowych. Unikaj wszystkich trzech dla dużych niesortowanych danych — zamiast tego użyj sortowań o złożoności O(n log n).
Te sortowania budują intuicję dotyczącą niezmienników, zamian i stabilności zanim przejdziesz do bardziej zaawansowanych algorytmów.
Sortowanie przez wstawianie w szczególności pojawia się wewnątrz produkcyjnych sortowań (takich jak Timsort) dla małych podtablic.
Zrozumienie, dlaczego mają złożoność O(n²), nadaje znaczenie przejściu do sortowań O(n log n).