Insertion Sort

Poin Penting

• ›Kasus terbaik O(n) pada data yang hampir terurut, sangat praktis
• ›Algoritma online: bisa mengurutkan elemen satu per satu saat datang
• ›Stable sort: elemen yang sama tetap pada urutan aslinya
• ›Dipakai sebagai tahap akhir pada hybrid sort seperti Timsort (Python, Java) untuk subarray kecil
• ›Efisien untuk input kecil (n < 20) karena overhead-nya rendah

Visualizer Interaktif

Contoh Kode

func insertionSort(_ arr: inout [Int]) {
    let n = arr.count
    for i in 1..<n {
        let key = arr[i]
        var j = i - 1
        while j >= 0 && arr[j] > key {
            arr[j + 1] = arr[j]
            j -= 1
        }
        arr[j + 1] = key
    }
}

var nums = [12, 11, 13, 5, 6]
insertionSort(&nums)
print(nums)  // [5, 6, 11, 12, 13]

Latihan Soal