Insertion sort

Saat bermain kartu, kamu biasanya mengambil kartu satu per satu dan menyisipkannya ke posisi yang tepat di antara kartu yang sudah dipegang. Itulah insertion sort.

1def insertion_sort(data):2    data = data.copy()3    for i in range(1, len(data)):4        kunci = data[i]5        j = i - 16        while j >= 0 and data[j] > kunci:7            data[j + 1] = data[j]8            j -= 19        data[j + 1] = kunci10    return data1112print(insertion_sort([12, 11, 13, 5, 6]))

[5, 6, 11, 12, 13]

Data yang lebih besar dari kunci digeser satu posisi ke kanan, sampai ditemukan tempat yang pas untuk kunci.

Analisis

• Terburuk (data terbalik): O(n²).
• Terbaik (data sudah urut): O(n), karena setiap data langsung berada di tempatnya.
• Sangat cepat untuk data yang hampir urut, misalnya daftar yang sudah urut lalu ditambah beberapa data baru.
• Stabil, karena data hanya digeser melewati data yang lebih besar, tidak yang sama besar.

Karena kelebihan ini, banyak algoritma pengurutan modern memakai insertion sort untuk potongan data yang kecil.

1def insertion_sort_hitung(data):2    data = data.copy()3    geser = 04    for i in range(1, len(data)):5        kunci = data[i]6        j = i - 17        while j >= 0 and data[j] > kunci:8            data[j + 1] = data[j]9            j -= 110            geser += 111        data[j + 1] = kunci12    return data, geser1314print(insertion_sort_hitung([1, 2, 3, 5, 4]))15print(insertion_sort_hitung([5, 4, 3, 2, 1]))

([1, 2, 3, 4, 5], 1)
([1, 2, 3, 4, 5], 10)