Insertion sort mengurutkan array kayak kamu menyusun kartu di tangan: ambil satu kartu baru, geser kartu yang lebih besar ke kanan, lalu sisipkan kartu itu di celahnya. Bagian kiri array selalu sudah urut, dan tiap pass menyisipkan satu angka lagi ke bagian itu.
🧪 Tebakan cepat: ada 1.000 angka yang sudah hampir urut, cuma dua angka yang tertukar. Insertion sort butuh sekitar 1.000 perbandingan, atau sekitar 500.000? Tebak dulu, jawabannya ada di bagian "Seberapa cepat".
Cara kerjanya
Urutkan [5, 2, 4, 6, 1, 3]. Angka pertama dianggap bagian yang sudah urut. Pass 1 mengambil angka kedua, pass 2 angka ketiga, dan seterusnya.
| Pass | Yang terjadi | Array sesudahnya |
|---|---|---|
| 1 | ambil 2: geser 5, lalu 2 masuk di depan | [2, 5, 4, 6, 1, 3] |
| 2 | ambil 4: geser 5, berhenti di 2 | [2, 4, 5, 6, 1, 3] |
| 3 | ambil 6: 5 gak lebih besar, 6 tetap | [2, 4, 5, 6, 1, 3] |
| 4 | ambil 1: geser 6, 5, 4 dan 2, lalu 1 masuk di depan | [1, 2, 4, 5, 6, 3] |
| 5 | ambil 3: geser 6, 5 dan 4, berhenti di 2 | [1, 2, 3, 4, 5, 6] |
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const current = arr[i]; // angka yang diambil, kayak kartu
let j = i - 1;
// geser yang lebih besar ke kanan
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current; // sisipkan
}
return arr;
}
console.log(insertionSort([5, 2, 4, 6, 1, 3]).join(",")); // 1,2,3,4,5,6
- Loop
formulai darii = 1, karena angka di index 0 gak punya tetangga kiri untuk dibandingkan. currentmenyimpan angka yang diambil. Begitu angka lain digeser,arr[i]ketimpa, jadi angkanya disimpan dulu.jmundur darii - 1. Selamaarr[j]lebih besar daricurrent,arr[j]digeser satu langkah ke kanan (arr[j + 1] = arr[j]).j >= 0menjaga supayajberhenti di ujung kiri array.- Begitu loop
whileberhenti, celahnya ada dij + 1, dancurrentditaruh di situ.
Insertion sort menggeser, bukan menukar: angka yang lebih besar pindah satu langkah ke kanan, dan current cuma ditulis sekali di akhir.
Seberapa cepat
Banyaknya data disebut n. Kerjanya tergantung seberapa berantakan datanya:
- Data terbalik (kasus terburuk) dan data acak: tiap angka digeser jauh ke kiri. Itu O(n²): datanya dua kali lipat, waktunya kira-kira empat kali lipat.
- Data sudah urut atau hampir urut (kasus terbaik): tiap angka cukup dibandingkan sekali dengan tetangga kirinya, lalu berhenti. Itu O(n): datanya dua kali lipat, waktunya dua kali lipat. Jawaban tebakan: sekitar 1.000 perbandingan saja.
Overhead-nya juga kecil. Overhead adalah kerja tambahan di luar membandingkan dan menggeser: insertion sort gak butuh array baru atau memori tambahan, dan kodenya pendek. Karena itu insertion sort sering dipilih untuk data kecil (puluhan isi) dan data yang hampir urut. Sort bawaan JavaScript di Chrome dan Node.js (Timsort) juga memakai insertion sort untuk potongan data yang pendek.
⚠️ Jebakan yang sering ketemu
- Mulai dari
i = 0. Angka pertama gak punya tetangga kiri. Mulai darii = 1. - Gak menyimpan
current. Kalau ditulisarr[j] > arr[i], nilaiarr[i]sudah ketimpa geseran, jadi hasilnya kacau. Simpan dulu diconst current = arr[i]. - Menyisipkan di
j. Sesudah loop,jmenunjuk angka yang gak lebih besar daricurrent, atau-1. Celahnya dij + 1. - Data besar yang acak. 100.000 angka acak bisa butuh sekitar 2,5 miliar langkah. Untuk itu pakai
arr.sort((a, b) => a - b).
🎯 Bubble, selection, atau insertion?
| Bubble sort | Selection sort | Insertion sort | |
|---|---|---|---|
| Tiap pass | tukar tetangga yang salah urut | cari yang terkecil, tukar sekali | sisipkan satu angka ke bagian kiri yang sudah urut |
| Data sudah urut | O(n) dengan swapped |
tetap O(n²) | O(n) |
| Banyak tukar | bisa O(n²) | paling banyak n - 1 | geser bisa O(n²) |
| Stabil | ya | tidak | ya |
Stabil artinya dua nilai yang sama tetap di urutan aslinya, misalnya dua siswa dengan nilai yang sama tetap di urutan daftar awal.
TL;DR: Insertion sort menjaga bagian kiri array tetap urut. Di tiap pass, dia mengambil satu angka (current), menggeser yang lebih besar ke kanan, lalu menyisipkannya di celah j + 1. Mulai dari i = 1. Kasus terburuknya O(n²), tapi untuk data yang sudah atau hampir urut cuma O(n), dan overhead-nya kecil. Makanya dia dipakai untuk data kecil dan di dalam sort bawaan seperti Timsort.
