Langkah-Langkah Pengurutan Insertion Sort

Insertion sort adalah metode pengurutan data dengan cara membandingkan 2 data pertama , diurutkan, lalu diperiksa.

Untuk lebih jelasnya, berikut proses Insertion Sort :

• Langkah pengurutan

0	1	2	3	4	5	6
2	15	20	5	13	25	7

Diberikan sebuah array bilangan : 2,15,20,5,13,25,7 diurutkan secara ascending (terkecil-terbesar)

Proses 1

Temp	Cek	Geser
15	Temp > 2	–

Menghasilkan :

0	1	2	3	4	5	6
2	15	20	5	13	25	7

Proses 2

Temp	Cek	Geser
20	Temp > 15	–
20	Temp > 2	–

Menghasilkan :

0	1	2	3	4	5	6
2	15	20	5	13	25	7

Proses 3

Temp	Cek	Geser
5	Temp < 20	Data ke-2 posisi 3
5	Temp < 15	Data ke-1 posisi 2
5	Temp > 2	–

Menghasilkan :

0	1	2	3	4	5	6
2	5	15	20	13	25	7

Proses 4

Temp	Cek	Geser
13	Temp < 20	Data ke-3 posisi 4
13	Temp < 15	Data ke-2 posisi 3
13	Temp > 5	–

Menghasilkan :

0	1	2	3	4	5	6
2	5	13	15	20	25	7

Proses 5

Temp	Cek	Geser
25	Temp > 20	–
25	Temp > 15	–
25	Temp > 13	–
25	Temp > 5	–
25	Temp > 2	–

Menghasilkan :

0	1	2	3	4	5	6
2	5	13	15	20	25	7

Proses 6

Temp	Cek	Geser
7	Temp < 25	Data ke-5 posisi 6
7	Temp < 20	Data ke-4 posisi 5
7	Temp < 15	Data ke-3 posisi 4
7	Temp < 13	Data ke-2 posisi 3
7	Temp > 5	–

Menghasilkan :

Array setelah diurutkan

Notasi Algoritmik Insertion Sort :

Implementasi dengan C:

#include <math.h>
#include <stdio.h>

//Program insertion sort
void insertionSort(int arr[], int n)
{
    int a, i, temp, j;
    for (i = 1; i < n; i++) {
        temp = arr[i];
        j = i - 1;
        while (j >= 0 && temp < arr[j]) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = temp;
        for(a = 0; a < n; a++){
            printf("%d ", arr[a]);
        }
        printf("\n");
    }
}

//Driver program
int main(){
    int arr[100];
    int n,a;
    
    //Input panjang array
    printf("Masukkan panjang array : ");
    scanf("%d", &n);
    
    //Input elemen array
    printf("Masukkan elemen array: \n");
    for(a = 0; a < n; a++){
        scanf("%d", &arr[a]);
    }
    
    //Array urut
    printf("\n Langkah-langkah pengurutan : \n");
    insertionSort(arr, n);
    
    return 0; 
}