Ini tiga algoritma pengurutan perbandingan O(n²) yang sederhana. Mereka lambat pada input besar tetapi mudah dipahami dan berguna untuk mengajarkan mekanika pengurutan.
Ini tiga algoritma pengurutan perbandingan O(n²) yang sederhana. Mereka lambat pada input besar tetapi mudah dipahami dan berguna untuk mengajarkan mekanika pengurutan.
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 benar-benar cepat untuk larik kecil atau hampir terurut dan digunakan dalam pengurutan hibrida. Hindari ketiganya pada data besar yang tidak terurut — gunakan pengurutan O(n log n) sebaliknya.
Pengurutan ini membangun intuisi tentang invarian, pertukaran, dan stabilitas sebelum Anda mengatasi algoritma lanjutan.
Insertion sort khususnya muncul dalam pengurutan produksi (seperti Timsort) untuk sub-larik kecil.
Memahami mengapa mereka O(n²) membuat lompatan ke pengurutan O(n log n) bermakna.
Pustaka soalan temu duga IT dengan jawapan terperinci — daripada Junior hingga Senior.
Derma