Insertion Sort

Insertion Sort adalah salah satu teknik mengurutkan data.

Kelebihan: Cepat pada data yang sebagian besar sudah terurut, codenya cukup singkat, dan stabil
Kekurangan: Tidak efektif (lambat) jika datanya banyak dan terurut secara terbalik (worst case)

Kompleksitas
Worst case/Average: O(n^2)
Best case (data sudah terurut): O(n)

Animasi visualnya dapat dilihat di visualgo.net/sorting.html
Penjelasan lebih lanjut dapat dilihat di en.wikipedia.org/wiki/Insertion_sort

Berikut code dan implementasinya dalam bahasa pemrograman C.

#include <stdio.h>

int main()
{   int N, i;

    // Input jumlah test case
    scanf("%d", &N);
   
    // Input Data
    int ar[N];
    for(i = 0;i < N;i++)
        scanf("%d", &ar[i]);
   
    //Insertion Sort
    int tmp, j;

    for(i = 1;i < N;i++)
    {
        tmp = ar[i];
        j = i - 1;
       
        while((ar[j] > tmp) && (j > -1))
        {
            ar[j + 1] = ar[j];
            j--;
        }
       
        ar[j + 1] = tmp;
    }
   
    // Output
    printf("%d", ar[0]);
    for(i = 1;i < N;i++)
        printf(" %d", ar[i]);
}

Contoh test case:
7
7 5 3 1 6 4 2

Contoh output:
1 2 3 4 5 6 7