Insertion Sort adalah salah satu jenis algoritma pengurutan dalam ilmu komputer yang memiliki karakteristik sederhana dan cukup efisien untuk mengelola daftar yang melibatkan sejumlah elemen yang tidak banyak. Tidak seperti algoritma pengurutan lainnya seperti Bubble Sort atau Merge Sort, Insertion Sort bekerja dengan membandingkan elemen-elemen yang berada dalam daftar dan kemudian memindahkannya ke posisi yang benar dalam daftar yang sudah diurutkan.
Berikut ini adalah alur kerja algoritma Insertion Sort:
- Inisialisasi Urutan: Dalam algoritma Insertion Sort, iterasi pertama melibatkan elemen pertama dan kedua dari daftar. Elemen pertama dinyatakan telah diurutkan.
- Pilih Elemen: Selanjutnya, elemen kedua dalam daftar diperiksa. Jika elemen ini lebih besar dari elemen pertama, tetap di tempatnya. Namun, jika lebih kecil, elemen ini dipindahkan ke posisi sebelum elemen pertama.
- Pengulangan Dalam List: Proses ini kemudian diulang untuk elemen berikutnya dalam daftar, membandingkannya dengan elemen-elemen sebelumnya. Jika itu lebih besar, tetapkan di tempat. Jika lebih kecil, geser ke posisi yang lebih tepat di urutan yang sedang diurutkan.
- Iterasi Melalui Seluruh List: Proses ini diulang sampai semua elemen dalam daftar telah diperiksa dan dipindahkan ke posisi yang tepat dalam urutan yang diurutkan.
- Hasil: Setelah semua elemen telah dipindahkan ke posisi yang tepat, daftar sekarang telah diurutkan sepenuhnya menggunakan algoritma Insertion Sort.
Visualisasi berikut dapat membantu memahami algoritma Insertion Sort:
Algoritma Insertion sort sangat sederhana untuk dipahami dan diimplementasikan, tetapi tidak begitu efisien untuk daftar yang lebih besar, karena kompleksitas waktu adalah O(n^2). Meskipun demikian, Insertion Sort mengungguli algoritma pengurut lainnya, khususnya untuk daftar kecil dan daftar yang hampir diurutkan, karena memiliki overhead operasional yang lebih kecil.
Insertion Sort sangat ideal untuk situasi di mana kita ingin meminimalkan penambahan data baru ke daftar yang telah diurutkan. Meskipun ada beberapa varian yang coba memperbaiki kekurangan dalam Insertion Sort, seperti Shell Sort yang mencoba mengurangi jumlah pergeseran yang dibutuhkan, Insertion Sort sendiri tetap menjadi algoritma dasar yang lebih disukai dalam banyak situasi.
Sebagai ringkasan, Insertion Sort adalah algoritma pengurutan sederhana dan efisien yang memutuskan posisi setiap elemen dalam sebuah list dengan membandingkan dengan elemen lain dalam urutan yang telah diurutkan. Meskipun agak lambat untuk daftar yang lebih besar, ini adalah pilihan yang sangat baik untuk ukuran data yang lebih kecil dan hampir diurutkan.
