Algoritma Insertion Sort

Insertion Sort

Insertion sort adalah metode pengurutan yang menggunakan 2 buah list dalam proses pengurutannya yaitu sorted list dan unsorted list, dimana pada awalnya semua angka yang kan di urutkan berada di unsorted list setelah itu index 0 dari unsorted list dipindahkan ke sorted list begitu juga index 1. Lalu index 0 dan 1 yang sudah dipindahkan ke sorted list akan dikomparasi mana yang memiliki nilai terkecil. Dan yang memiliki terkecil itu akan menjadi index 0, begitulah seterusnya dimana tiap index yang baru masuk dari unsorted list ke sorted list akan dikomparasi dengan semua index yang sudah lebih dahulu masuk ke sorted list. Proses ini akan terus berulang sampai semua index yang ada di unsorted list pindah ke sorted list dan dikomparasi, maka hasil pengurutan akan terlihat. Berikut contoh dari Insertion Sort :

Langkah 1

Asumsikan kita memiliki array dengan 5 elemen, seperti berikut :

Selanjutnya angka pada index 0 dan 1 akan dipindahkan ke sorting list, setelah itu di sorted list angka pada index 0 dan 1 akan dikomparasi untuk mencari index yang memiliki nilai terkecil dan dikarenakan nilai pada index 0 lebih kecil dari nilai index 1 maka tidak terjadi perubahan posisi. Dan hasilnya dapat dilihat seperti gambar dibawah ini :

Langkah 2

Pada langkah ini pindahkan angka pada index 2 ke sorted list, dimana ketika angka pada index 2 memasuki sorted list angka tersebut akan dikomparasi dengan angka pada index 0 dan 1 dan dimana hasilnya angka pada index 2 diposisikan di index 1. Hasil komparasinya dapat dilihat pada gambar berikut :

Langkah 3

Masukkan angka pada index 3 ke sorted list, dan karena nilai pada index 3 lebih kecil dari nilai pada index 0, 1, dan 2 maka nilai pada index 3 diposisikan di index 0.

Langkah 4

Dan langkah terakhir adalah memasukkan nilai pada index 4 kedalam sorted list, dan ternyat nilai pada index 4 lebih kecil jika dibandingkan dengan nilai pada index 1, 2, dan 3 maka nilai pada index 4 diposisikan pada index 2.

Dengan hasil yang mucul maka proses pengurutan dengan metode insertion sort sudah selesai.

Berikut adalah algoritma dari Insertion Sort :

Insertion_Sort(A)

1.    Deklarasi Array A

2.    Deklarasi Elemen

3.    Input elemen array A

4.    Input nilai elemen-elemen array A

5.    For i=1 sampai i < elemen

6.          While i > 0

7.                    If A[i-1] > A[i]

8.                          Tukar A[i-1] dengan A[i]

9.                          i-1 

10.                 end if     

11.      end while

12. end for

Dan berikut adalah flowchart dari Insertion Sort :

Dan untuk implementasi dari algoritma insertion sort dengan bahasa pemrograman dapat dilihat di postingan ane yg ini :

Implementasi Algoritma Insertion Sort dengan C#

Sekian postingan dari ane moga bermanfaat, bila ada kesalahan mohon dikoreksi dan harap dimaklumi karena ane masih newbie :Peace: