Is iad seo trí algartam simplí O(n²) comparáide a ordúchán. Bíonn siad mall ar ionchuir mhóra ach tá siad éasca a thuiscint agus úsáideach do theagasc na meicníocanna ordaithe.
Is iad seo trí algartam simplí O(n²) comparáide a ordúchán. Bíonn siad mall ar ionchuir mhóra ach tá siad éasca a thuiscint agus úsáideach do theagasc na meicníocanna ordaithe.
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]
| Ord | An Bhreáthéad | An Saghas | Seasmhach | In-áit |
|---|---|---|---|---|
| Balúin | O(n) | O(n²) | Sea | Sea |
| Roghnaithe | O(n²) | O(n²) | Níl | Sea |
| Ionsáite | O(n) | O(n²) | Sea | Sea |
Tá ord ionsáite i ndáiríre tapa do thacair beag nó beagnach-ordaithe agus úsáidtear é taobh istigh de ordaithí hibrideacha. Seachnaigh na trí cinn ar shonraí mór neamhordaithe — úsáid ordaithí O(n log n) ina ionad.
Tógann na ordaithí seo intuisíon do invariants, dealúchán, agus seasmhacht sula dtéann tú i ngleic le halgartam ardteicníochta.
Bíonn ord ionsáite go háirithe ann taobh istigh d'ordaithí táirgthe (ar nós Timsort) do fho-ehilimintí an-bheag.
A bheith ar eolas ar cén fáth gur O(n²) a bhíonn siad a dhéanann an t-fhoghlaimh go dtí ordaithí O(n log n) ábhartha.