Pemrograman C++ : Insertion Sort

Insertion sort merupakan salah satu dari beberapa metode dari algoritma sorting yang digunakan banyak pemrogram. Insertion sort mirip dengan bubble sort, perbedaanya adalah dalam bubble sort, setiap elemen array yang dimasukkan terlebih dahulu, kemudian disorting satu persatu, sedangkan pada insertion sort, elemen-elemen dimasukkan satu per satu, kemudian disorting hingga semua elemen telah masuk dan terurut. bisa dibilang, algoritma insertion sort lebih rapih dibandingkan dengan bubble sort.

Kita akan masuk ke penjelasan singkat mengenai insertion sort. Berikut adalah algoritma dari insertion sort :

for i = 0 to n
    j = i
    while(j < 0 AND elemen[j] < elemen[j-1])
        swap(elemen[j], elemen[j-1])
        j = j - 1

Pada bagian “<“, dapat kita ubah bergantung kebutuhan yang kita inginkan. Jika menginginkan hasil ascending (dari kecil ke besar) maka gunakan tanda “<“, namun jika menginginkan hasil descending (dari besar ke kecil), gunakan tanda “>”

Cara kerja dari insertion sort adalah sebagai berikut :

array = {4, 5, 1, 6, 3}
proses sorting (ascending) :
1 :
  4

2 : 
  4, 5
  (tidak ada perubahan posisi)

3 :
  4, 5, 1
  4, 1, 5
  1, 4, 5

4 :
  1, 4, 5, 0
  1, 4, 0, 5
  1, 0, 4, 5
  0, 1, 4, 5

5 :
  0, 1, 4, 5, 3
  0, 1, 4, 3, 5
  0, 1, 3, 4, 5
  (proses berhenti)

Begitulah proses kerja dari algoritma insertion sort. dapat dipahami bahwa fungsi dari variabel “i” adalah sebagai pengiterasi jumlah elemen yang diproses serta fungsi dari variabel “j” adalah sebagai pengiterasi proses sorting per satu elemen. Variabel “j” memiliki nilai maksimum sama dengan “i”, oleh karena itu, jumlah maksimum proses pengurutan sebuah elemen adalah sama dengan posisi ke berapa elemen tersebut diinputkan, berdasarkan pada pembatas “j < 0”. Namun, jika elemen telah menemukan tempat yang tepat, maka proses akan terhenti, berdasarkan pada pembatas “elemen[j] < elemen[j-1]” atau “elemen[j] > elemen[j-1]”.

Berikut adalah contoh kode dalam bahasa C++ :

Untuk contoh programnya dapat dilihat di sini.

Demikianlah penjelasan tentang insertion sort. Semoga bermanfaat dan dapat menambah ilmu 🙂