Konsep Insertion Sort
Algoritma insertion sort adalah sebuah algoritma sederhana yang cukup efisien untuk mengurutkan sebuah list yang hampir terurut. Algorima ini juga bisa digunakan sebagai bagian dari algoritma yang lebih canggih.
Cara kerja algoritma ini adalah dengan mengambil elemen list satu-per-satu dan memasukkannya di posisi yang benar seperti namanya. Pada array, list yang baru dan elemen sisanya dapat berbagi tempat di array, meskipun cukup rumit.
Untuk menghemat memori, implementasinya menggunakan pengurutan di tempat yang membandingkan elemen saat itu dengan elemen sebelumnya yang sudah diurut, lalu menukarnya terus sampai posisinya tepat. Hal ini terus dilakukan sampai tidak ada elemen tersisa di input.
Salah satu implementasinya pada kehidupan sehari-hari adalah saat kita mengurutkan kartu remi. Kita ambil kartu satu persatu lalu membandingkan dengan kartu sebelumnya untuk mencari posisi yang tepat.
Variasi pada umunya yang dilakukan terhadap array pada insertion sort adalah sebagai berikut :
- Elemen awal di masukkan sembarang, lalu elemen berikutnya dimasukkan di bagian paling akhir.
- Elemen tersebut dibandingkan dengan elemen ke (x-1). Bila belum terurut posisi elemen sebelumnya digeser sekali ke kanan terus sampai elemen yang sedang diproses menemukan posisi yang tepat atau sampai elemen pertama.
- Setiap pergeseran akan mengganti nilai elemen berikutnya, namun hal ini tidak menjadi persoalan sebab elemen berikutnya sudah diproses lebih dahulu.
Insertion sort ini memiliki beberapa keuntungan :
- Implementasi yang sederhana
- Paling efisien untuk data berukuran kecil
- Merupakan online algorithmic, yang berarti bisa langsung melakukan sort setiap ada data baru
- Proses di tempat (memerlukan O(1) memori tambahan)
- Stabil.
Pada tahun 2004 Bender, Farach-Colton, and Mosteiro menemukan pengembangan baru dari algoritma ini, disebut library sort atau gapped insertion sort yang menggunakan beberapa gap kosong di sepanjang array. Dengan algoritma ini, pergeseran elemen dilakukan sampai gap tersebut dicapai. Algoritma ini cukup baik dengan kompleksitas O(n log n).
Simulasi Insertion Sort
Berikut ini adalah contoh dari simulasi Insertion Sort.
 |
| Simulasi Insertion Sort |
Setiap satu kali Pass akan ada satu nilai yang disisipkan. Kemudain pada Pass n-1 data akan terurut. Data yang telah terurut diberi warna abu-abu. Panah menunjukkan perubahan posisi nilai yang akan di-insert.
Notasi Algoritmik Insertion Sort
Procedure InsertionSort (Input/Output T: TabInt, Input N: integer) {mengurut tabel integer [1 .. N] dengan Insertion Sort secara ascending}
Kompleksitas Algoritma Insertion Sort
Algoritma Insertion Sort juga terdiri dari 2 kalang bersarang. Dimana terjadi N-1 Pass (dengan N adalah banyak elemen struktur data), dengan masing-masing Pass terjadi i kali operasi perbandingan. i tersebut bernilai 1 untuk Pass pertama, bernilai 2 untuk Pass kedua, begitu seterusnya hingga Pass ke N-1.
Secara Kompleksitas, selection sort dan insertion sort mempunyai Big-Oh yang sama. Walaupun begitu, insertion sort sebenarnya lebih mangkus. Perhatikan gambar berikut:
 |
| Grafik Kompleksitas Insertion Sort |
Berdasarkan gambar, Insertion Sort 40% lebih cepat daripada Selection Sort. Namun, Insertion Sort mempunyai kekurangan. Insertion Sort lebih baik tidak digunakan untuk menangani struktur data dengan lebih dari 2000 elemen