Insertion sort meniru cara manusia menyusun kartu: kita ambil satu kartu dari tumpukan dan sisipkan ke posisi yang tepat di tangan terurut. Walaupun kompleksitas worst case-nya O(n^2), insertion sort sangat cepat pada data yang hampir terurut—best case O(n). Algoritma ini juga stabil dan in-place, menjadikannya pilihan populer untuk dataset kecil atau sebagai bagian dari algoritma hybrid seperti Timsort. Pada chapter ini kita akan mengimplementasikan insertion sort dan menghitung jumlah perbandingan serta geseran untuk memahami kapan ia unggul.

Cara Kerja Insertion Sort #

Algoritma menjaga array terbagi menjadi bagian terurut (kiri, dari indeks 0 sampai i-1) dan bagian belum terurut (kanan, dari i sampai n-1). Pada setiap iterasi:

  1. Ambil elemen a[i] sebagai kunci.
  2. Geser elemen di bagian terurut yang lebih besar dari kunci satu posisi ke kanan.
  3. Letakkan kunci di posisi yang tepat.

Best case terjadi pada data yang sudah terurut: setiap iterasi hanya butuh satu perbandingan (a[j] > kunci langsung false), tanpa ada geseran. Total n-1 perbandingan—kompleksitas O(n). Worst case pada data terbalik: setiap elemen baru harus digeser sampai ke depan. Total 1 + 2 + ... + (n-1) = n(n-1)/2 operasi—kompleksitas O(n^2).

Implementasi Dasar #

c 
#include <stdio.h>

/* Insertion sort: sisipkan elemen ke bagian terurut */
void insertion_sort(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int kunci = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > kunci) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = kunci;
    }
}

static void cetak(const int *a, int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[] = {12, 11, 13, 5, 6, 8, 1, 9};
    int n = sizeof(a) / sizeof(a[0]);

    printf("Sebelum: ");
    cetak(a, n);

    insertion_sort(a, n);

    printf("Setelah: ");
    cetak(a, n);

    return 0;
}

Output yang Dihasilkan:

text 
Sebelum: 12 11 13 5 6 8 1 9 
Setelah: 1 5 6 8 9 11 12 13

Array terurut menaik. Insertion sort adalah algoritma stabil karena kita hanya menggeser elemen yang lebih besar dari kunci (bukan >=), sehingga urutan relatif elemen yang sama nilainya tetap dipertahankan.

Mari kita telaah baris-baris kode di atas:

  1. Baris 5 (for (int i = 1; i < n; i++)): loop luar mulai dari indeks 1. Elemen pertama dianggap sebagai bagian terurut dengan satu elemen.
  2. Baris 6 (int kunci = a[i];): simpan elemen yang akan disisipkan ke variabel sementara. Langkah ini penting karena posisi a[i] akan ditimpa oleh geseran.
  3. Baris 7 (int j = i - 1;): inisialisasi pointer j ke elemen terakhir bagian terurut.
  4. Baris 8-11 (while (j >= 0 && a[j] > kunci)): loop sambil menggeser elemen yang lebih besar dari kunci satu posisi ke kanan. Setiap iterasi: a[j+1] = a[j] lalu j--. Loop berhenti saat j < 0 atau a[j] <= kunci.
  5. Baris 12 (a[j + 1] = kunci;): sisipkan kunci ke posisi yang tepat. Pakai j + 1 karena j sudah digeser mundur satu langkah di akhir loop.
  6. Baris 17-19 (cetak): helper untuk verifikasi sebelum dan sesudah sorting.

Menghitung Perbandingan dan Geseran #

Kita akan membandingkan jumlah operasi pada tiga skenario data untuk memahami karakteristik insertion sort.

c 
#include <stdio.h>

/* Insertion sort dengan penghitung perbandingan dan geser */
void insertion_count(int *a, int n, long long *banding, long long *geser) {
    *banding = 0;
    *geser = 0;
    for (int i = 1; i < n; i++) {
        int kunci = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > kunci) {
            (*banding)++;
            a[j + 1] = a[j];
            (*geser)++;
            j--;
        }
        if (j >= 0) (*banding)++;
        a[j + 1] = kunci;
    }
}

int main(void) {
    int a1[] = {12, 11, 13, 5, 6};
    int a2[] = {1, 2, 3, 4, 5};
    int a3[] = {5, 4, 3, 2, 1};
    int n = 5;

    long long b, g;

    insertion_count(a1, n, &b, &g);
    printf("Acak    : banding=%lld, geser=%lld\n", b, g);

    insertion_count(a2, n, &b, &g);
    printf("Terurut : banding=%lld, geser=%lld\n", b, g);

    insertion_count(a3, n, &b, &g);
    printf("Terbalik: banding=%lld, geser=%lld\n", b, g);

    return 0;
}

Output yang Dihasilkan:

text 
Acak    : banding=9, geser=7
Terurut : banding=4, geser=0
Terbalik: banding=10, geser=10

Pengamatan penting:

  • Data terurut: hanya 4 perbandingan (satu per iterasi) dan 0 geseran. Best case O(n).
  • Data terbalik: 10 perbandingan dan 10 geseran—sesuai rumus n(n-1)/2 = 10 untuk n=5. Worst case O(n^2).
  • Data acak: di antara dua kasus ekstrem. Average case O(n^2) dengan konstanta lebih rendah dari bubble sort.

Kapan Insertion Sort Cocok Dipakai #

Insertion sort adalah pilihan masuk akal pada situasi berikut:

  • Data hampir terurut: best case O(n) sangat efisien.
  • Ukuran data kecil (n < 50): overhead rendah, sering mengalahkan algoritma O(n log n) pada ukuran kecil.
  • Stability diperlukan: algoritma stabil secara default.
  • Online sorting: data datang satu per satu dan harus tetap terurut (insertion sort dapat menginsert elemen baru dalam O(n)).
  • Memori terbatas: algoritma in-place dengan O(1) ruang tambahan.

Sebaliknya, insertion sort tidak cocok bila:

  • Data besar dan acak: kompleksitas O(n^2) lambat.
  • Data terbalik: worst case dengan banyak geseran.