Penjelasan insertion sort: cara kerja, kode, dan kompleksitas

Ide dasar dengan kata-kata sederhana

Anggap elemen pertama sebagai list terurut dengan panjang satu. Ambil elemen kedua dan sisipkan sebelum atau sesudah elemen pertama. Ambil elemen ketiga dan sisipkan ke tempat yang tepat di antara dua elemen pertama. Lanjutkan sampai semua elemen telah disisipkan.

Untuk menyisipkan, simpan elemen baru di samping (sebut key), lalu telusuri bagian terurut ke kiri. Setiap elemen yang lebih besar dari key bergeser satu posisi ke kanan. Ketika sampai pada elemen yang tidak lebih besar, atau awal list, letakkan key di slot kosong.

Contoh langkah demi langkah

Urutkan [12, 11, 13, 5, 6]. Bagian sebelum garis sudah terurut (tetapi belum final).

Perhatikan langkah 2: elemen yang sudah di tempatnya hanya butuh satu perbandingan. Itulah sebabnya insertion sort cepat pada input yang hampir terurut.

Implementasi Python

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

Menggeser alih-alih menukar menulis setiap elemen yang dipindahkan satu kali, sekitar separuh pekerjaan versi berbasis pertukaran. Anda juga bisa mencari titik penyisipan dengan binary search, seperti di bawah. Ini menurunkan perbandingan menjadi O(n log n) total, tetapi pergeserannya tetap O(n²), sehingga waktu keseluruhan tetap O(n²).

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

Kompleksitas waktu dan ruang

Lebih tepatnya, waktu eksekusinya O(n + I), dengan I adalah jumlah inversi (pasangan yang urutannya salah). Jika setiap elemen berjarak paling jauh k posisi dari tempat akhirnya, I paling banyak n · k, sehingga insertion sort O(n · k): sangat cepat ketika k kecil.

Perbandingan insertion sort dengan sort lain

Insertion sort stabil karena elemen hanya bergerak ke kiri melewati elemen yang benar-benar lebih besar. Algoritma ini juga bersifat online: bisa mengurutkan data saat data datang, dengan prefiks terurut di setiap saat. Untuk list pendek, overhead-nya yang rendah mengalahkan algoritma O(n log n), sehingga Timsort (dipakai Python, dan Java untuk objek) mengurutkan run pendek dengan binary insertion sort, dan banyak implementasi quicksort beralih ke insertion sort di bawah ukuran kecil tertentu.

Varian dan kesalahan umum

• Binary insertion sort: binary search untuk mencari posisi, lalu geser. Perbandingan lebih sedikit, yang membantu ketika perbandingan itu mahal.
• Shell sort: jalankan insertion sort pada elemen yang berjarak tertentu (gap), lalu perkecil gap hingga 1. Algoritma ini memindahkan elemen yang jauh dengan cepat dan jauh lebih cepat daripada insertion sort biasa pada array besar.
• Insertion sort pada linked list: tidak perlu menggeser, tetapi mencari posisinya tetap berupa pemindaian linear.

Kapan memakai insertion sort

Pakai untuk array kecil (puluhan elemen), untuk data yang hampir terurut, seperti list yang sudah diurutkan lalu ditambah beberapa item, dan ketika Anda butuh sort stabil di tempat yang sederhana. Untuk data acak yang besar, pakai sort O(n log n); di Python itu berarti sorted() atau list.sort(), yang secara internal sudah menerapkan insertion sort pada run kecil.

Pertanyaan wawancara sering meminta penelusuran, kasus terbaik dan terburuk, alasan algoritma ini stabil, atau mengapa ia mengalahkan algoritma O(n log n) pada input kecil dan hampir terurut.