Ini adalah tiga sort perbandingan sederhana O(n²). Mereka lambat pada input besar tetapi mudah dipahami dan berguna untuk mengajarkan mekanik pengurutan.
Ini adalah tiga sort perbandingan sederhana O(n²). Mereka lambat pada input besar tetapi mudah dipahami dan berguna untuk mengajarkan mekanik 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 | Terbaik | Terburuk | Stabil | Di tempat |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ya | Ya |
| Selection | O(n²) | O(n²) | Tidak | Ya |
| Insertion | O(n) | O(n²) | Ya | Ya |
Insertion sort benar-benar cepat untuk array kecil atau hampir terurut dan digunakan di dalam sort hybrid. Hindari ketiga-tiganya pada data besar yang tidak disortir — gunakan sort O(n log n) sebagai gantinya.
Sort-sort ini membangun intuisi untuk invarian, pertukaran, dan stabilitas sebelum Anda menangani algoritma lanjutan.
Insertion sort khususnya muncul di dalam sort produksi (seperti Timsort) untuk subarray yang sangat kecil.
Mengetahui mengapa mereka adalah O(n²) membuat lompatan ke sort O(n log n) bermakna.
Perpustakaan pertanyaan wawancara IT dengan jawaban mendetail — dari Junior hingga Senior.
Donasi