Pengurutan: Insertion Sort

Gambaran besar dulu

Bayangin kamu lagi main kartu remi sama teman. Setiap kali dapat kartu baru, kamu nggak lempar begitu aja ke tangan, kamu sisipkan di posisi yang pas di antara kartu-kartu yang sudah kamu pegang.

Kartu yang sudah ada di tangan = sudah terurut. Kartu baru dari dek = belum terurut, perlu dicari tempatnya.

Nah, itulah insertion sort. Nama “insertion” sendiri artinya penyisipan. Jadi algoritmanya bekerja dengan cara menyisipkan elemen satu per satu ke posisi yang benar, sampai semua elemen akhirnya terurut.

Mudah? Seharusnya iya.

Konsep dua zona

Bayangkan mejamu dibagi dua wilayah:

| ZONA TERURUT (kiri) | ZONA BELUM TERURUT (kanan) |

• Zona kiri = kartu yang sudah rapi di tangan
• Zona kanan = sisa kartu yang belum diambil

Awalnya, zona kiri cuma berisi satu elemen pertama. Kenapa? Karena satu angka sendirian sudah otomatis “terurut”, nggak ada yang perlu dibandingkan.

Simulasi lengkap: daftar [5, 2, 8, 1, 9, 3, 7, 4]

Kita pakai notasi ini:

• Angka dalam kurung kotak [ ] = zona terurut
• Angka setelah tanda | = zona belum terurut

Kondisi awal:

[5] | 2  8  1  9  3  7  4

Elemen pertama (5) langsung masuk zona terurut.

Langkah 1 – ambil angka 2:

Ambil 2. Bandingkan dengan 5.

• 2 < 5? Ya. Geser 5 ke kanan, sisipkan 2 di depannya.
• Perbandingan: 1 kali. Pertukaran: 1 kali.

[2, 5] | 8  1  9  3  7  4

Langkah 2 – ambil angka 8:

Ambil 8. Bandingkan dengan 5.

• 8 > 5? Ya. Berarti 8 sudah ada di posisi benar, tidak perlu digeser.
• Perbandingan: 1 kali. Pertukaran: 0 kali.

[2, 5, 8] | 1  9  3  7  4

Langkah 3 – ambil angka 1:

Ambil 1. Bandingkan dari kanan ke kiri:

• 1 < 8? Geser 8.
• 1 < 5? Geser 5.
• 1 < 2? Geser 2.
• Sudah habis. Sisipkan 1 di paling kiri.
• Perbandingan: 3 kali. Pertukaran: 3 kali.

[1, 2, 5, 8] | 9  3  7  4

Langkah 4 – ambil angka 9:

Ambil 9. Bandingkan dengan 8.

• 9 > 8? Ya. Langsung tempatkan di ujung kanan zona terurut.
• Perbandingan: 1 kali. Pertukaran: 0 kali.

[1, 2, 5, 8, 9] | 3  7  4

Langkah 5 – ambil angka 3:

Ambil 3. Bandingkan dari kanan ke kiri:

• 3 < 9? Geser 9.
• 3 < 8? Geser 8.
• 3 < 5? Geser 5.
• 3 > 2? Berhenti. Sisipkan 3 setelah 2.
• Perbandingan: 4 kali. Pertukaran: 3 kali.

[1, 2, 3, 5, 8, 9] | 7  4

Langkah 6 – ambil angka 7:

• 7 < 9? Geser 9.
• 7 < 8? Geser 8.
• 7 > 5? Berhenti. Sisipkan 7 setelah 5.
• Perbandingan: 3 kali. Pertukaran: 2 kali.

[1, 2, 3, 5, 7, 8, 9] | 4

Langkah 7 – ambil angka 4:

• 4 < 9? Geser.
• 4 < 8? Geser.
• 4 < 7? Geser.
• 4 < 5? Geser.
• 4 > 3? Berhenti. Sisipkan 4 setelah 3.
• Perbandingan: 5 kali. Pertukaran: 4 kali.

[1, 2, 3, 4, 5, 7, 8, 9]

Selesai. Semua terurut dari kecil ke besar.

Rekap total perbandingan dan pertukaran

Aturan main Insertion Sort (versi simpel)

1. Mulai dari elemen kedua (elemen pertama dianggap sudah terurut).
2. Ambil elemen dari zona kanan.
3. Bandingkan dengan elemen di zona kiri, mulai dari yang paling kanan.
4. Selama elemen zona kiri lebih besar, geser satu posisi ke kanan.
5. Begitu ketemu elemen yang lebih kecil atau sama, sisipkan elemen tadi di sana.
6. Ulangi sampai zona kanan kosong.

Aktivitas fisik: 8 siswa = 8 kartu

Ini cara prakteknya di kelas:

• Cetak atau tulis angka [5, 2, 8, 1, 9, 3, 7, 4] di kertas karton besar, satu angka per kartu.
• Delapan siswa berdiri berjajar, masing-masing pegang satu kartu, hadapkan ke penonton.
• Siswa paling kiri = posisi pertama (zona terurut, hanya dia sendiri dulu).
• Satu per satu, siswa berikutnya “keluar dari barisan,” lalu jalan mencari posisi yang tepat sambil teman-temannya yang sudah terurut mundur satu langkah jika perlu.
• Catat setiap langkah di papan: berapa kali terjadi perbandingan dan pergeseran.

Ini bukan sekadar permainan. Begitulah persis cara komputer menjalankan Insertion Sort di memori.

Jebakan umum yang sering terjadi

• Lupa berhenti lebih awal. Banyak siswa terus membandingkan sampai paling kiri meskipun sudah ketemu angka yang lebih kecil. Ingat: begitu ketemu angka yang lebih kecil, berhenti dan sisipkan.
• Bingung arah perbandingan. Perbandingan selalu dari kanan ke kiri (dari dekat ke jauh ke zona terurut), bukan dari kiri ke kanan.
• Mengira harus menukar dua elemen. Insertion Sort bukan menukar seperti Bubble Sort. Yang terjadi adalah penggeseran: elemen yang lebih besar “mundur” satu posisi, bukan bertukar tempat secara langsung.
• Melewati elemen yang sudah tepat. Kalau angka baru lebih besar dari semua yang ada di zona terurut, langsung taruh di ujung kanan zona terurut — tidak perlu diproses lebih lanjut.

3 pertanyaan kuis

1. Diberikan daftar [3, 1, 4, 1, 5]. Setelah Langkah 1 (mengambil angka 1 dan memrosesnya), bagaimana bentuk zona terurut?
2. Pada daftar yang sudah terurut sempurna seperti [1, 2, 3, 4, 5], apakah Insertion Sort tetap perlu melakukan perbandingan? Berapa total perbandingan yang terjadi, dan berapa pertukaran?
3. Kenapa saat mengambil elemen baru, kita membandingkannya mulai dari elemen paling kanan zona terurut, bukan dari paling kiri?