Insertion sort algoritma dan contohnya dalam pemrograman C++, C , java dan PHP

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Untuk mempermudah pemahaman Anda, algoritma insertion sort kita analogikan dengan pengurutan kartu. Anggaplah Anda hendak mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang bernilai paling besar. Berikut penganalogiannya:

Semuanya dimulai dari posisi tangan kosong dan semua kartu masih tersimpan di atas meja. Anggap saja Anda hendak menyusun kartu ke tangan kiri Anda.
Anda lalu mengambil kartu pertama dari meja dan menyimpannya di tangan kiri.Kemudian, Anda mengambil kartu kedua dari meja. Lalu, Anda membandingkan kartu tersebut dengan kartu yang ada di tangan kiri.
Jika kartu yang baru saja diambil dari meja memiliki nilai yang lebih kecil daripada kartu di tangan kiri, maka kartu tersebut akan diletakan di depan kartu pembanding
Kartu yang telah dibandingkan akan bergeser mundur.
Proses ini akan terus berlangsung sampai semua kartu terurut dengan benar sesuai kriteria pengurutannya.
Setelah semua kartu terurut, satu set kartu yang sudah terurut akan disimpan kembali ke meja

Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.

Demikian juga halnya dalam pengurutan data.

Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

Berikut adalah simulasi Algoritma Insertion Sort.

Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

angka diatas adalah angka yang akan kita urutkan dengan inserting sort.

langkah pertama yang kita lakukan adalah ambil elemen pertama dari angka tersebut yaitu angka 6. karena angka 6 adalah angka pada elemen pertama maka tidak ada pertukaran. perhatikan gambar diatas.

kemudian lanjut ke element ke 2 yaitu angka 5. cek apakah angka lima lebih kecil dari angka sebelumnya (angka kiri) jika iya maka geser angka sebelumnya ke kanan. perhatikan gambar dibawah ini angka 5 berpindah ke element pertama.

lanjut ke element ke 3 yaitu angka 3. cek apakah angka 3 lebih kecil dari angka sebelumnya ? jika iya maka geser angka sebelumnya ke kanan.

lanjut ke element ke 4 yaitu angka 1. cek apakah angka 1 lebih kecil dari angka sebelumnya? jika iya maka geser angka yang lebih besar darinya ke kanan.

lanjut ke element ke 5 yaitu angka 8. karena angka 8 tidak lebih kecil dari angka sebelumnya maka angka 8 tetap diposisi element ke 5.

lanjut ke elemen ke 6 yaitu angka 7. cek apakah angka 7 lebih kecil dari sebelumnya. jika iya maka geser angka yang lebih besar darinya ke kanan.

lanjut ke element ke 8 yaitu angka 2. cek apakah angka 2 lebih kecil dari angka sebelumnya? jika iya geser angka yang lebih besar ke kanan.

lanjut ke element ke 9 yaitu angka 4. cek apakah angka 4 lebih kecil dari angka sebelumnya? jika iya geser angka yang lebih besar dari angka 4 ke kanan.
hasil akhir dari sorting di atas adalah sebagai berikut :