Nämä ovat kolme yksinkertaista O(n²) vertailusorttia. Ne ovat hitaita suurissa syötteissä, mutta helppo ymmärtää ja hyödylliset lajittelumekaniikan opettamiseen.
Nämä ovat kolme yksinkertaista O(n²) vertailusorttia. Ne ovat hitaita suurissa syötteissä, mutta helppo ymmärtää ja hyödylliset lajittelumekaniikan opettamiseen.
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]
| Lajittelu | Paras | Huonoin | Vakaa | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Kyllä | Kyllä |
| Selection | O(n²) | O(n²) | Ei | Kyllä |
| Insertion | O(n) | O(n²) | Kyllä | Kyllä |
Insertion sort on todella nopea pienille tai lähes lajitelluille taulukoille ja sitä käytetään hybridisorteissa. Vältä kaikkia kolmea suurissa lajittelemattomissa tiedoissa — käytä sen sijaan O(n log n) -sorteja.
Nämä sortit rakentavat intuitiota invarianteista, vaihdoista ja vakaasta järjestyksestä ennen kuin ryhdyt edistyneisiin algoritmeihin.
Insertion sort erityisesti näkyy tuotantosortissa (kuten Timsort) pienille ali-ryhmille.
Tiedon siitä, miksi ne ovat O(n²), tekee hyppyn O(n log n) -sorteihin merkitykselliseksi.