Insertion Sort

Insertion sort meniru cara manusia menyusun kartu di tangan: ambil satu kartu, geser kartu-kartu yang lebih besar ke kanan, lalu sisipkan kartu baru ke celah yang terbentuk. Algoritma ini menjadi O(n) pada data hampir terurut dan stabil sehingga sering dipakai sebagai sub-rutin pada hybrid sort seperti introsort (yang dipakai std::sort). Pada Chapter ini kita akan membedah mekanisme insertion sort, mengimplementasikannya, dan menjelaskan mengapa algoritma ini menjadi pilihan untuk sub-array kecil. Pada akhir chapter kita akan paham mengapa insertion sort masih relevan meskipun secara asimptotik O(n²).

Aturan: Sisipkan ke Posisi Benar #

Pada setiap iterasi i dari 1 hingga n-1:

1. Simpan key = v[i].
2. Bandingkan key dengan v[i-1], v[i-2], ... secara mundur.
3. Geser elemen yang lebih besar dari key satu posisi ke kanan.
4. Sisipkan key ke posisi yang tepat (sebelum elemen yang lebih besar).

Setelah iterasi i selesai, v[0..i] terurut.

Mekanisme Kerja #

Tiap iterasi menempatkan satu elemen baru ke posisi yang benar dalam bagian already-sorted v[0..i].

Kode: Insertion Sort dengan Instrumentasi #

#include <iostream>
#include <vector>
#include <utility>

void insertion_sort(std::vector<int>& v, long long& cmp, long long& shift) {
    cmp = 0;
    shift = 0;
    for (std::size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0) {
            ++cmp;
            if (v[j] > key) {
                v[j + 1] = v[j];
                ++shift;
                --j;
            } else break;
        }
        v[j + 1] = key;
    }
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {5, 4, 3, 2, 1};
    long long cmp, shift;
    insertion_sort(a, cmp, shift);
    std::cout << "Worst case [5,4,3,2,1]:\n  hasil   = "; print(a);
    std::cout << "  cmp    = " << cmp << ", shift = " << shift << '\n';

    std::vector<int> b = {1, 2, 3, 4, 5};
    insertion_sort(b, cmp, shift);
    std::cout << "\nBest case [1,2,3,4,5]:\n  hasil   = "; print(b);
    std::cout << "  cmp    = " << cmp << ", shift = " << shift << '\n';

    std::vector<int> c = {1, 2, 3, 5, 4, 6, 7};
    insertion_sort(c, cmp, shift);
    std::cout << "\nHampir terurut [1,2,3,5,4,6,7]:\n  hasil   = "; print(c);
    std::cout << "  cmp    = " << cmp << ", shift = " << shift << '\n';

    return 0;
}

Output yang Dihasilkan:

Worst case [5,4,3,2,1]:
  hasil   =  1 2 3 4 5
  cmp    = 10, shift = 10

Best case [1,2,3,4,5]:
  hasil   =  1 2 3 4 5
  cmp    = 4, shift = 0

Hampir terurut [1,2,3,5,4,6,7]:
  hasil   =  1 2 3 4 5 6 7
  cmp    = 7, shift = 1

Bedah Kode Baris-per-Baris #

1. int key = v[i];: simpan elemen yang akan disisipkan ke variabel sementara key. Langkah ini penting karena v[i] akan ditimpa saat pergeseran.
2. int j = static_cast<int>(i) - 1;: indeks pembanding, dimulai dari elemen sebelum i.
3. while (j >= 0): loop mundur hingga awal array atau hingga ditemukan posisi yang benar.
4. ++cmp;: catat setiap pembandingan untuk instrumentasi.
5. if (v[j] > key): bandingkan dengan > (strict greater). Stabilitas terjaga karena elemen yang equal (v[j] == key) tidak digeser — key tetap berada setelah v[j] sesuai urutan input.
6. v[j + 1] = v[j]; ++shift; --j;: geser elemen yang lebih besar satu posisi ke kanan, catat pergeseran, lanjut ke elemen sebelumnya.
7. v[j + 1] = key;: tempatkan key pada posisi yang benar — celah yang ditinggalkan setelah pergeseran.
8. Output worst case [5,4,3,2,1]: cmp = 10 = n(n-1)/2 = 5·4/2, shift = 10. Sesuai formula worst case Θ(n²).
9. Output best case [1,2,3,4,5]: cmp = 4 = n-1, shift = 0. Setiap iterasi hanya satu pembandingan (langsung break). Kompleksitas Θ(n).
10. Output hampir terurut: cmp = 7 (1+1+1+2+1+1 = 7 untuk n=7), shift = 1. Insertion sort adaptif terhadap data hampir terurut — inilah alasan ia menjadi sub-rutin introsort.

Kompleksitas #

Best case O(n) tercapai bila array sudah terurut — hanya n-1 pembandingan dengan 0 pergeseran. Inilah yang membuat insertion sort unik dibanding bubble dan selection sort.

Stabilitas #

Insertion sort stabil. Pembandingan memakai v[j] > key (strict greater), sehingga elemen yang equal dengan key tidak digeser. Akibatnya key (yang berasal dari indeks lebih besar) selalu ditempatkan setelah elemen equal yang sudah ada — urutan relatif terjaga.

In-Place #

Insertion sort in-place dengan O(1) memori tambahan. Hanya variabel key, i, dan j yang dialokasikan.

Mengapa Insertion Sort Dipakai pada std::sort #

std::sort di libstdc++ dan libc++ mengimplementasikan introsort — kombinasi:

1. Quick sort untuk partisi awal.
2. Heap sort bila kedalaman rekursi melebihi 2·log₂ n (menghindari worst case quick sort).
3. Insertion sort bila ukuran sub-array ≤ 16 (cutoff).

Alasan insertion sort dipilih untuk sub-array kecil:

• Konstanta kecil — tidak ada overhead rekursi atau pemanggilan fungsi.
• Adaptif — pada data hampir terurut (sering terjadi setelah quick sort selesai), kompleksitas mendekati O(n).
• Stabil relatif terhadap posisi elemen equal di sub-array.
• Branch predictor modern bekerja sangat baik pada loop sederhana insertion sort.

Kode: Insertion Sort pada Sub-array STL #

#include <iostream>
#include <vector>
#include <algorithm>

void insertion_sort_range(std::vector<int>& v, int lo, int hi) {
    for (int i = lo + 1; i <= hi; ++i) {
        int key = v[i];
        int j = i - 1;
        while (j >= lo && v[j] > key) {
            v[j + 1] = v[j];
            --j;
        }
        v[j + 1] = key;
    }
}

int main() {
    std::vector<int> v = {9, 3, 7, 1, 8, 2, 6, 5, 4, 0};
    int n = static_cast<int>(v.size());

    // Sort 6 elemen pertama saja dengan insertion sort
    insertion_sort_range(v, 0, 5);

    std::cout << "Sort v[0..5] dengan insertion sort:\n";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';

    // Sekarang sort sisanya dengan std::sort
    std::sort(v.begin() + 6, v.end());
    std::cout << "Sort v[6..9] dengan std::sort:\n";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

Sort v[0..5] dengan insertion sort:
 1 2 3 7 8 9 6 5 4 0
Sort v[6..9] dengan std::sort:
 1 2 3 7 8 9 0 4 5 6

1. insertion_sort_range(v, lo, hi): varian yang menerima batas [lo, hi] — berguna sebagai sub-rutin hybrid sort.
2. j >= lo: batas bawah indeks — mencegah akses di luar rentang.
3. Output pertama: sub-array v[0..5] terurut menjadi 1 2 3 7 8 9, sedangkan v[6..9] tetap 6 5 4 0.
4. std::sort(v.begin() + 6, v.end()): STL dapat mengurutkan sub-array dengan iterator range.

Binary Insertion Sort #

Pembandingan linear dapat diganti dengan binary search untuk menemukan posisi penyisipan dalam O(log i). Sayangnya, pergeseran elemen tetap O(i) sehingga total tetap O(n²). Binary insertion sort berguna bila biaya pembandingan tinggi (misalnya string panjang) tetapi tidak mengubah asimptotik.

int find_pos(const std::vector<int>& v, int lo, int hi, int key) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (v[mid] <= key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

1. v[mid] <= key: gunakan <= (bukan <) agar tetap stabil — posisi penyisipan adalah setelah elemen equal terakhir.
2. Kompleksitas binary search: O(log i) per iterasi vs O(i) linear.
3. Total kompleksitas: pembandingan O(n log n) tetapi pergeseran tetap O(n²).

Kapan Insertion Sort Layak Dipakai #

• n kecil (< 16–32) — konstanta kecil, sering lebih cepat daripada quick sort.
• Data hampir terurut — best case O(n).
• Sebagai sub-rutin hybrid sort (introsort, timsort).
• Online sorting — elemen datang satu per satu dan harus segera disisipkan.

Ringkasan #

• Insertion sort menyisipkan elemen ke posisi yang benar dengan menggeser elemen yang lebih besar ke kanan.
• Best case O(n) (data hampir terurut), average dan worst O(n²).
• Stabil dan in-place (O(1) memori tambahan).
• Menjadi sub-rutin pada std::sort (introsort) untuk sub-array kecil — bukti relevansi algoritma O(n²) di dunia modern.
• Variasi binary insertion sort mempercepat pembandingan menjadi O(log n) per iterasi tetapi pergeseran tetap O(n).

Pada chapter berikutnya kita akan naik kelas ke algoritma divide and conquer: merge sort dengan kompleksitas O(n log n) yang dijamin pada semua kasus.