Insertion Sort: Algoritma Klasik untuk Pemula Hingga Pro

Oleh Samuel Wirajaya (website)

Co-founder, Acutis Academy. Software Engineer eks-FAANG, penggemar UNIX & Linux.

Petunjuk: Klik ikon Bendera untuk memulai demonstrasi Snap!

Dalam demonstrasi di atas, kita dapat mengamati proses yang terjadi dalam algoritma Insertion Sort yang digunakan pada saat komputer mengurutkan data. Maka pada kesempatan ini saya akan melakukan sebuah kupas tuntas (deep dive) mengenai algoritma yang digunakan dalam demo tersebut.

Apa itu Insertion Sort?

Dalam ilmu komputer, algoritma Insertion Sort adalah sebuah cara sederhana untuk mengurutkan sejumlah data yang tersimpan dalam suatu array (jajaran) dengan menyelipkan (insert) data satu-demi-satu ke tengah sejumlah data yang sudah benar urutannya.

Insertion sort mudah dipahami karena algoritma ini sangat mirip dengan bagaimana kebanyakan orang mengurutkan sejumlah kartu remi yang dipegang saat main kartu.

Implementasi pertama: kartu remi

Insertion sort bekerja dengan cara memindahkan elemen satu-per-satu dari tempat asalnya ke posisi yang tepat. Elemen-elemen yang sudah terurutkan dikumpulkan di bagian awal array.

Mari kita ambil contoh langkah demi langkah, kali ini dengan membayangkan sejumlah kartu remi di tangan kita yang perlu kita urutkan.

Dalam contoh ini, di tangan kita, kita akan mengumpulkan kartu-kartu yang sudah berurutan di awal tumpukan kartu di tangan kita (yang artinya di sebelah kiri.)

Saat ini hanya ada satu kartu yang kita bisa jamin “terurut,” yakni kartu pertama, atau kartu paling kiri.
Bandingkan kartu ke-2 dengan kartu ke-1. Kalau kartu kedua lebih besar dari kartu pertama, kita tukar dengan kartu pertama. Dengan demikian kita punya dua kartu yang urutannya sudah benar.
Periksa kartu ketiga, bandingkan dengan dua kartu pertama, dan selipkan di tempatnya sehingga tiga kartu pertama benar urutannya.
Lihat kartu keempat, bandingkan dengan tiga kartu pertama, dan selipkan di tempatnya sehingga empat kartu pertama benar urutannya.
Lihat kartu kelima, bandingkan dengan empat kartu pertama, dan selipkan di tempatnya sehingga lima kartu pertama benar urutannya.
Demikian seterusnya sehingga semua kartu sudah diperiksa dan benar urutannya.

Implementasi kedua: dengan array di komputer

Sketsa 1: Cara menyelipkan/insertion. Dalam suatu array di komputer, suatu elemen bisa diselipkan di antara elemen lainnya dengan cara tukar-menukar (swap). Misalnya, jika kita ingin menyelipkan Elemen 4 menjadi di antara Elemen 1 dan Elemen 2, kita bisa menukar 3 dan 4, lalu 2 dan 3:

Tugas: Selipkan 'B' di antara 'a' dan 'f':
a f g B E I H D C J
------------------------------------------
Pelaksanaan:
a f g B E I H D C J
a f B g E I H D C J  setelah tukar(3, 4)
a B f g E I H D C J  setelah tukar(2, 3)

Sketsa 2: Mengetahui bahwa posisi selipan sudah benar. Ciri bahwa elemen yang sedang diselipkan posisinya sudah benar adalah bahwa elemen itu lebih besar (atau sama dengan) dari elemen yang sebelumnya. Maka proses tukar-menukar di atas akan diulang-ulang selama elemen yang di sebelah kirinya lebih besar dari dia (yang artinya urutannya belum benar.)

Tugas: Selipkan 'E' di tempat yang benar:
a b f g E I H D C J

Asumsi: 4 elemen pertama yakni a, b, f, g sudah terurut.
-----------------------------------------------------------------
Pelaksanaan:
a b f g E I H D C J
a b f E g I H D C J  setelah tukar(4,5) karena G > E
a b E f g I H D C J  setelah tukar(3,4) karena F > E
a b E f g I H D C J  apakah B > E? tidak, maka tugas ini selesai!

Sketsa 3: Meneruskan untuk semua elemen. Meneruskan contoh di atas, kita pun akan selanjutnya menyelipkan I ke tempat yang benar, lalu menyelipkan H ke tempat yang benar, lalu D dan demikian seterusnya.

Jika kita mendapatkan array dengan urutan yang acak, maka kita bisa memulai dengan “menyelipkan” elemen kedua, lalu ketiga, lalu keempat, dan demikian seterusnya hingga elemen terakhir. Maka pada akhirnya array itu akan menjadi berurutan.

Kode pseudo. Maka dengan sketsa-sketsa di atas, kita bisa menulis kode sebagai berikut untuk melaksanakan insertion sort.

for i = 2 hingga panjang(Array):  # -- lihat sketsa 3
    j = i
    while j > 1 and Array.elemenKe(j - 1) > Array.elemenKe(j):  # -- sket. 2
        Array.tukar(j - 1, j)     # -- sket. 1
        j = j - 1

Latihan soal untuk Anda: Cari implementasi lainnya yang tidak menggunakan tukar-menukar, namun menggunakan satu variabel sementara untuk memegang elemen yang sedang disisipkan.

Kekurangan dan kelebihan Insertion Sort

Insertion sort memiliki beberapa kelebihan yang membuatnya menjadi pilihan yang baik di beberapa situasi:

Implementasi sederhana. Insertion Sort mudah dipahami dan diimplementasikan, membuatnya menjadi pilihan yang baik untuk pemula dalam bidang algoritmika.
Beban overhead yang minimal. Algoritma lainnya mungkin “secara teori” lebih cepat, namun, misalnya, pada kenyataannya membutuhkan panggilan fungsi rekursif, atau permohonan alokasi memori tambahan kepada sistem operasi, atau CPU cache miss yang makan waktu. (CPU waktu cache miss: Eh barusan elemen yang ini apa ya? Bentar saya cek dulu di RAM.)

Namun, insertion sort juga memiliki kelemahan yang patut diketahui oleh para programmer:

Performa yang lambat. Jika kita mencoba algoritma insertion sort di atas secara manual dengan kartu remi betulan, kita akan merasakan sendiri bagaimana mencari tempat untuk menyelipkan kartu akan menjadi semakin sulit seiring waktu. Sama halnya jika suatu komputer melaksanakan insertion sort, performanya akan lebih lambat dibandingkan algoritma sort yang lain, terutama saat mendekati penghujung data.
Tidak cocok untuk data yang besar. Karena performanya yang lambat, insertion sort tidak cocok digunakan untuk sorting data yang besar, misalnya array yang isinya 16 elemen atau lebih.

Kapan menggunakan Insertion Sort?

Insertion sort memiliki beberapa aplikasi nyata di industri perkomputeran, di mana kelebihannya membuat insertion sort menjadi pilihan yang unggul karena memiliki overhead yang sangat kecil dibandingkan algoritma sort lainnya.

Maka mengingat overhead-nya yang kecil, aplikasi nyata dari insertion sort adalah:

Mengurut data yang kecil. Kalau pokok permasalahannya adalah panjang array, maka kita bisa saja membatasi penggunaan insertion sort untuk array yang singkat. Nyatanya, insertion sort adalah pilihan yang sangat baik untuk mengurut data yang berjumlah sedikit.
Mengurut data yang hampir terurut. Jika data sudah hampir terurut, insertion sort bahkan bisa mengalahkan algoritma sort lainnya untuk array yang panjang sekalipun. Jika data sudah terurut dengan benar, algoritma insertion sort dipastikan akan tidak melakukan operasi apapun selain memeriksa urutan data, meminimalkan waktu yang terbuang.
Penggabungan dengan algoritma lainnya. Algoritma insertion sort seringkali dipadukan dengan algoritma lainnya seperti quicksort untuk mengurangi overhead dari algoritma tersebut dan meningkatkan performa lebih lanjut lagi.
Sistem embedded. Insertion sort juga menjadi algoritma pilihan ketika memrogram sebuah mikrokontroler dengan memori dan daya pengolahan yang sangat terbatas, untuk digunakan sebagai komponen dalam barang-barang elektronik.

Kesimpulan

Dengan demikian, kita bisa melihat bahwa Insertion Sort adalah sebuah algoritma pengurutan data yang sederhana namun efektif yang memiliki tempat yang istimewa di dunia ilmu komputer. Sifatnya yang intuitif membuatnya menjadi pilihan yang baik untuk para pemula dan penggemar, sedangkan berbagai keunggulannya menjadikannya sebuah alat yang berguna bagi para programmer, para profesional ilmu komputer, dan cendekiawan lainnya.

Catatan kaki untuk “programmer sepuh”

Array di dalam pseudocode di atas adalah array yang one-indexed demi alasan konsistensi dengan bahasa Snap! yang kami ajarkan kepada pemula dalam kurikulum kami. Operator and juga harus “konslet” karena pada saat kondisi not (j > 1), maka array.elemenKe(j - 1) tidak boleh dijalankan karena array tidak mempunyai elemen ke-nol.

Kami juga tidak mau mengajarkan Bubble Sort kepada pemula karena insertion sort sudah terbukti lebih baik dibandingkan bubble sort dalam segala hal (Astrachan, 2003) dan insertion sort memiliki kegunaan yang nyata di dalam industri sekalipun itu adalah algoritma sort “kelas kakap” atau O(n²). Contohnya adalah implementasi std::stable_sort dalam GNU libstdc++ (Github) untuk array yang memiliki kurang dari 15 elemen.