Insertion Sort merupakan sebuah teknik pengurutan dengan cara membandingkan dan mengurutkan dua data pertama pada array, kemudian membandingkan data para array berikutnya apakah sudah berada di tempat semestinya. Algorithma insertion sort seperti proses pengurutan kartu yang berada di tangan kita. Algorithma ini dapat mengurutkan data dari besar ke kecil (Ascending) dan kecil ke besar (Descending). Algoritma ini tidak cocok untuk set data dengan jumlah besar karena kompleksitas dari algorithma ini adalah Ο() di mana n adalah jumlah item.

Berikut gambaran dari implementasi Insertion Sort:

1st Cycle:
(70, 60, 30, 50, 40, 20) -> (60, 70, 30, 50, 40, 20)
(60, 70, 30, 50, 40, 20)

2nd Cycle:
(60, 70, 30, 50, 40, 20) -> (60, 30, 70, 50, 40, 20)
(60, 30, 70, 50, 40, 20) -> (30, 60, 70, 50, 40, 20)
(30, 60, 70, 50, 40, 20)

3rd Cycle:
(30, 60, 70, 50, 40, 20) -> (30, 60, 50, 70, 40, 20)
(30, 60, 50, 70, 40, 20) -> (30, 50, 60, 70, 40, 20)
(30, 50, 60, 70, 40, 20) -> (30, 50, 60, 70, 40, 20)
(30, 50, 60, 70, 40, 20)

4th Cycle:
(30, 50, 60, 70, 40, 20) -> (30, 50, 60, 40, 70, 20)
(30, 50, 60, 40, 70, 20) -> (30, 50, 40, 60, 70, 20)
(30, 50, 40, 60, 70, 20) -> (30, 40, 50, 60, 70, 20)
(30, 40, 50, 60, 70, 20) -> (30, 40, 50, 60, 70, 20)
(30, 40, 50, 60, 70, 20)

5th Cycle:
(30, 40, 50, 60, 70, 20) -> (30, 40, 50, 60, 20, 70)
(30, 40, 50, 60, 20, 70) -> (30, 40, 50, 20, 60, 70)
(30, 40, 50, 20, 60, 70) -> (30, 40,20, 50, 60, 70)
(30, 40, 20, 50, 60, 70) -> (30, 20, 40, 50, 60, 70)
(30, 20, 40, 50, 60, 70) -> (20, 30, 40, 50, 60, 70)
(20, 30, 40, 50, 60, 70)

Berikut implementasi dari Insertion Sort menggunakan Bahasa C:

#include<stdio.h>

 

int main(){

int arr[]={70,60,30,50,40,20};

int n = sizeof(arr)/sizeof(int);

int k,y,i;

for(k=1; k < n; k++) {

y = arr[k];

for(i=k-1; i >= 0 && y < arr[i]; i–){

arr[i+1] = arr[i];

}

arr[i+1] = y;

}

 

for(int i=0;i<n;i++){

printf(“%d “,arr[i]);

}

 

return 0;

}

Reference:

Paul Deitel & Harvey Deitel. (2016). C how to program : with an introduction to C++. 08. Pearson  Education. Hoboken. ISBN: 9780133976892.