Hizi ni algoriti tatu rahisi za O(n²) za kulinganisha mtazamo. Zina polepole juu ya ingizo kubwa lakini rahisi kuelewa na muhimu kwa kufundisha mechanics ya kuorodhesha.
Hizi ni algoriti tatu rahisi za O(n²) za kulinganisha mtazamo. Zina polepole juu ya ingizo kubwa lakini rahisi kuelewa na muhimu kwa kufundisha mechanics ya kuorodhesha.
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]
| Oda | Bora | Mbaya | Imara | Mahali |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ndiyo | Ndiyo |
| Selection | O(n²) | O(n²) | Hapana | Ndiyo |
| Insertion | O(n) | O(n²) | Ndiyo | Ndiyo |
Insertion sort ni haraka kwa kweli kwa kamba ndogo au karibu kusanikishwa na hutumiwa ndani ya oda ya hybrid. Kuepuka zote tatu kwa data kubwa isiyosortwa — tumia oda za O(n log n) badala yake.
Hizi oda zinajenga hekima kwa invariants, mabadilisho, na imara kabla ya kukabili algoriti za juu.
Insertion sort hasa inaonekana ndani ya oda za utengenezaji (kama Timsort) kwa safu ndogo.
Kujua kwa nini ni O(n²) inafanya kuruka kwa oda za O(n log n) kuwa matahadisha.