Estas são três simples classificações por comparação O(n²). Elas são lentas em entradas grandes, mas fáceis de entender e úteis para ensinar a mecânica de ordenação.
Estas são três simples classificações por comparação O(n²). Elas são lentas em entradas grandes, mas fáceis de entender e úteis para ensinar a mecânica de ordenação.
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]
| Classificação | Melhor | Pior | Estável | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Sim | Sim |
| Selection | O(n²) | O(n²) | Não | Sim |
| Insertion | O(n) | O(n²) | Sim | Sim |
Insertion sort é genuinamente rápido para arrays pequenos ou quase ordenados e é usado dentro de classificações híbridas. Evite os três em dados grandes não ordenados — use classificações O(n log n) em vez disso.
Estas classificações constroem intuição para invariantes, trocas e estabilidade antes de você lidar com algoritmos avançados.
Insertion sort em particular aparece dentro de classificações em produção (como Timsort) para subarrays minúsculos.
Saber por que eles são O(n²) torna o salto para classificações O(n log n) significativo.