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.

Penganalogian Insertion Sort dengan pengurutan kartu

Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

• Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
• Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
• Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
• Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).

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

Kasus Terbaik (Best-Case)

Kasus terbaik dalam algoritma insertion short adalah ketika array yang menjadi inputan sudah terurut. Hal ini dikarenakan penyisipan semacam memiliki waktu berjalan linear (yaitu, O (n)). Selama setiap iterasi, elemen sisa pertama dari input hanya elemen paling kanan dari bagian yang diurutkan dari array.

Kasus Terburuk (Worst-Case)

Kasus terburuknya adalah ketika input array yang menjadi masukan terurut/telah tersortir namun dalam urutan yang terbalik. Karena proses dalam algoritma ini mengurutkan satu persatu dari index pertama sampai index terakhir, sehingga jika array dalam keadaan terurut terbalik akan membutuhkan waktu yang sangat lama. Dalam kasus ini setiap loop tunggal akan memindai dan menggeser seluruh bagian yang diurutkan dari array sebelum memasukkan elemen berikutnya. Ini memberikan penyisipan semacam waktu berjalan kuadrat (yaitu, O (n2)).

Kasus Rata-rata (Average-Case)

Kasus rata-rata juga kuadratik, yang membuat semacam penyisipan tidak praktis untuk menyortir array besar. Namun, penyisipan adalah salah satu algoritma tercepat untuk menyortir array yang sangat kecil, bahkan lebih cepat daripada quicksort. Memang, implementasi cepat baik dari penyisipan semacam untuk array menggunakan lebih kecil dari ambang tertentu, juga ketika timbul sebagai subproblem.

TASK: Contoh pengerjaan soal

1. Show the results of each pass of InsertionSort applied to the list

[7, 3, 9, 4, 2, 5, 6, 1, 8].

Answer:

List = [7, 3, 9, 4, 2, 5, 6, 1, 8]

Iterasi 1 [3,7 , 9, 4, 2, 5, 6, 1, 8]

Iterasi 2 [3,4,7 , 9, 2, 5, 6, 1, 8]

Iterasi 3 [2,3,4,7 , 9, 5, 6, 1, 8]

Iterasi 4 [2,3,4,7 , 9, 5, 6, 1, 8]

Iterasi 5 [2,3,4, 5,7 , 9, 6, 1, 8]

Iterasi 6 [2,3,4, 5, 6,7 , 9, 1, 8]

Iterasi 7 [1, 2,3,4, 5, 6,7 , 9, 8]

Iterasi 8 [1, 2,3,4, 5, 6,7 ,8, 9]

Hasil akhir pada iterasi ke 8. Dalam iterasi diatas hanya ditampilkan urutan setiap hasil dari proses insertion. Dalam proses sebenarnya, setiap proses iterasi terjaid pembandingan antara value dari index yang sedang dibandingkan, dengan setiap index di sisi sebelah kiri. Jika lebih kecil maka akan digeser dan sampai pada posisi dimana seharusnya dia berada.

2. Show the results of each pass of InsertionSort applied to the list

[3, 5, 2, 9, 8, 1, 6, 4, 7]

Answer:

List [3, 5, 2, 9, 8, 1, 6, 4, 7]

Iterasi 1 [2, 3, 5, 9, 8, 1, 6, 4, 7]

Iterasi 2 [2, 3, 5, 8,9, 1, 6, 4, 7]

Iterasi 3 [1, 2, 3, 5, 8,9, 6, 4, 7]

Iterasi 4 [1, 2, 3, 5, 6, 8,9, 4, 7]

Iterasi 5 [1, 2, 3, 4, 5, 6, 8,9, 7]

Iterasi 6 [1, 2, 3, 4, 5, 6, 7, 8,9]

Hasil akhir pada iterasi ke 6. Dalam iterasi diatas hanya ditampilkan urutan setiap hasil dari proses insertion. Dalam proses sebenarnya, setiap proses iterasi terjaid pembandingan antara value dari index yang sedang dibandingkan, dengan setiap index di sisi sebelah kiri. Jika lebih kecil maka akan digeser dan sampai pada posisi dimana seharusnya dia berada.