Ezek három egyszerű O(n²) összehasonlítási rendezés. Lassúak a nagy bemenetek esetén, de könnyen érthetőek és hasznosak a rendezés mechanikájának tanítására.
Ezek három egyszerű O(n²) összehasonlítási rendezés. Lassúak a nagy bemenetek esetén, de könnyen érthetőek és hasznosak a rendezés mechanikájának tanítására.
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]
| Rendezés | Legjobb | Legrosszabb | Stabil | Helybeli |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Igen | Igen |
| Selection | O(n²) | O(n²) | Nem | Igen |
| Insertion | O(n) | O(n²) | Igen | Igen |
Az insertion sort valóban gyors kis vagy majdnem rendezett tömbök esetén, és hibrid rendezések használnak belül. Kerülje ezt a hármat nagy, nem rendezett adatokon — használjon helyette O(n log n) rendezéseket.
Ezek a rendezések intuíciót építenek fel az invariánsok, cserék és stabilitás tekintetében, mielőtt haladó algoritmusokkal foglalkozna.
Az insertion sort különösen megjelenik a gyártási rendezéseken (például Timsort) belül kis altömbök esetén.
Annak megértése, hogy miért O(n²) az ezek, értelmezsé teszi az O(n log n) rendezésekre való ugrást.