Insertion-sort

insertion-sort.c

/*
INSERTION-SORT(A)
1 for j ← 2 to length[A]
2   do key ← A[j]
3	<> Insert A[j] into the sorted sequence A[1...j - 1].
4	i ← j - 1
5	while i > 0 and A[i] > key
6	    do A[i + 1] ← A[i]
7		i ← i - 1
8	A[i + 1] ← key
*/

#include <stdio.h>

void INSERTION_SORT(int A[], int length)
{
   int j = 0;
   int i = 0;
   int key = 0;

   for(j=2; j<length; j++)
   {
       key = A[j];
       //Insert A[j] into the sorted sequence A[1...j - 1].
       i = j - 1; 
       while(i > 0 && A[i] > key)
       {
           A[i+1] = A[i];
	   i = i - 1;
       }
       A[i+1] = key;
   }
}

int main()
{
   int A[] = {0, 5, 2, 4, 6, 1, 3};
   int i = 0;
   
   int length = sizeof(A)/sizeof(int);
   INSERTION_SORT(A, length);

   for(i=1; i<length; i++)
   {
      printf("%d, ", A[i]);
   } 
   getchar();
}