Questi sono tre semplici O(n²) algoritmi di ordinamento per confronto. Sono lenti su input grandi ma facili da capire e utili per insegnare la meccanica dell'ordinamento.
Questi sono tre semplici O(n²) algoritmi di ordinamento per confronto. Sono lenti su input grandi ma facili da capire e utili per insegnare la meccanica dell'ordinamento.
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 | Best | Worst | Stable | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |
Insertion sort è genuinamente veloce per array piccoli o quasi ordinati ed è usato dentro gli algoritmi ibridi. Evita tutti e tre su dati grandi non ordinati — usa invece algoritmi O(n log n).
Questi algoritmi costruiscono intuizione su invarianti, scambi e stabilità prima di affrontare algoritmi avanzati.
Insertion sort in particolare appare dentro gli algoritmi di ordinamento in produzione (come Timsort) per piccoli sottovettori.
Capire perché sono O(n²) rende significativo il salto agli algoritmi O(n log n).
Una raccolta di domande di colloquio IT con risposte dettagliate — da Junior a Senior.
Dona