Contoh Program Algoritma Insertion Sort C++ beserta penjelasan

Contoh Program Algoritma Insertion Sort c++ – banyak sekali algoritma sorting yang bisa kita gunakan, salah satu yang sering dipelajari adalah Insertion Sort, algoritma ini simple dan tidak memakan banyak memory.

apa itu insertion sort

Insertion Sort adalah sebuah algoritma pengurutan(sorting) baik ascending maupun descending yang bekerja layaknya bermain kartu menggunakan tangan.

algoritma ini sangatlah simple dan mudah diperaktekan, selain itu algoritma ini juga tidak memerlukan penggunaan if layaknya algoritma bubble sort dan algoritma sorting lainnya.

algoritma ini sangat bagus digunakan bila data yang diurutkan jumlahnya besar

baca juga: contoh program algoritma quick sort c++

penjelasan algoritma insertion sort

seperti yang saya katakan diatas, algoritma ini bekerja seperti bermain kartu, bayangkan ada 5 kartu di atas meja dengan urutan:

algoritma insertion sort dimulai dari index array ke 1 yang berarti dimulai dari angka 8.

setiap perulangan kita akan membandingkan angka disebelah kirinya hingga angka tersebut lebih besar daripada angka disebelah kirinya. disini angka 8 lebih besar daripada angka 2 jadi tidak ada perubahan.

lanjut masuk ke angka 5, disini angka 5 lebih kecil dibanding angka disebelah kirinya yaitu 8.tapi dia lebih besar dibanding 2, jadi angka 5 akan masuk diantara 2 dan 8. sedangkan angka 8 bergeser ke kanan.

selanjutnya angka 3, disini angka 3 lebih kecil dibanding 8 dan 5 tapi lebih besar dibanding 2, maka angka 3 akan bergeser 2 langkah ke kiri, sedangkan angka 5 dan 8 akan bergeser 1 langkah ke kanan.

selanjutnya angka 9, karena ia lebih besar daripada 8, maka posisinya tidak berubah.

dan terakhir angka 4, disii angka 4 lebih kecil dibanding angka 5,8,9 maka ia bergeser 3 langkah ke kiri dan angka 5,8,9 bergeser 1 langkah ke kanan.

jadi algoritma ini sama halnya seperti kita mengurutkan kartu diatas meja, dimana kita menggeser kartunya hingga menemukan posisi yang pas.

baca juga : Contoh program bubble sort c++

kelebihan algoritma insertion sort

• Salah satu algoritma Sorting tercepat
• sangat cocok untuk melakukan sorting dengan jumlah data yang besar
• karena list langsung di sort di tempat, maka tidak memerlukan memory tambahan untuk menjalankannya

kelemahan algoritma insertion sort

• Jika data sebelumnya sudah di ada yang ter sorting maka algoritma ini kurang efisien, karena ia akan mengecek seluruh data di dalam list.
• lebih cocok mensorting bilangan yang bentuknya bulat.

Baca Juga: Contoh program algoritma Merge Sort

contoh program insertion sort C++

Penjelasan

Line 5-8 : Disini, kita menyiapkan variable untuk menampung inputan dari user, dimana variable y adalah banyaknya data dan array x adalah wadah untuk data yang akan diinputkan.

Line 9-13 : Disini kita melakukan perulangan untuk mengisi index dari setiap array, mulai dari array ke[0] sampai array ke y;

Line 14-27 : Disinilah proses sorting terjadi, pertama kita akan memulai perulangan dimulai dari array index ke 1 yang di implementasikan kedalam variable i. variable i akan menjadi kunci untuk dibandingkan dengan bilangan sebelumnya. jika bilangan sebelumnya lebih besar, maka key akan kembali dibandingkan dengan bilangan ke 2 sebelum i, dst hingga menemukan bilangan yang lebih kecil daripada i;

Line 22-25 : disini kita menampilkan hasil dari setiap perulangan.

Line 29-31 : Disini kita menampilkan hasil akhir dari proses sorting

output

itulah Contoh Program Algoritma Insertion Sort c++, semoga bermanfaat