Algoritma insertion sort adalah salah satu algoritma pengurutan dengan cara menyisipkan (insert) jika menemukan nilai yang lebih kecil, sehingga algoritma ini menyelesaikan pengurutan secara bertahap dairi kiri ke kanan atau sebaliknya. Proses pengurutan dimulai dari data ke 2. Ilustrasinya mirip seperti saat menyisipkan kartu di permainan kartu. Agar lebih mudah dalam memahaminya silahkan perhatikan ilustrasi gambar berikut ini:
Agar lebih memahami cara pengurutan dengan algoritma insert sort, silahkan liat gambar di bawah :
Contoh Program Insertion Sort pada PHP
<html> <head> <title>Sorting2</title> </head> <body> <h3 style="text-decoration:underline";>Insertion Sort</h3> <?php $size=6; $data=array(0,1,2,3,4,5); $data[0]=6; $data[1]=10; $data[2]=3; $data[3]=2; $data[4]=9; $data[5]=4; echo("<b>Jumlah Data : 6</b><br/>"); echo("<b>Data Awal :</b> "); tampildata(); insert_sort(); echo "<font color='red'><b>Hasil Akhir : "; tampildata(); echo "<b></font><br/>"; function tampildata() { global $data; for($i=0;$i<=5;$i++) { echo "$data[$i] "; } echo "<br/>"; } function insert_sort() { global $data,$size; for($i=0;$i<=$size-1;$i++) { $value=$data[$i]; $j=$i-1; $NoIterasi=$i+1; echo " <font color='blue'>"; echo " Iterasi Ke-$NoIterasi : "; tampildata(); echo "</font>"; while(($j>=0)&&($data[$j]>$value)) { $data[$j+1]=$data[$j]; $j=$j-1; $data[$j+1]=$value; tampildata(); } } } ?> </body> </html>
Gambar diatas dipahami aja satu satu proses jalannya, sekarang lita lihat source code dari fungsi insertion sort .
for (i = 1 ; i <= n - 1; i++)
{
j = i;
while ( j > 0 && data[j] < data[j-1])
{
temp = data[j];
data[j] = data[j-1];
data[j-1] = temp;
j--;
}
}
Sekian. Semoga Bermanfaat
