C Programming Challenge #02: Sort - insertion

Following article will discuss how to implement insertion sort in C. Sorting is a activity of arranging elements in order. Order can be increasing or decreasing. Insertion sort is type of sorting. Insertion sort is efficient method for sorting a small number of elements. Insertion sort is very similar to people use when sorting the playing cards. We start with a empty hand and cards down on the table. We pick up one card from the table and insert it in the correct position into the cards that are present in left hand. To find the correct position for card we compare it with each card already in the hand from right to left.

 It can be depicted in below picture.

Strategy:

• Lets have the number in array name 'a'.
• Sorting will be done by function sort_insert that has following prototype
• int sort_insert(int *arr, int max);
• arr is pointer to array where the data is there.
• max is the length of the array.
• Lets have a function print_array that will help us print the content of the array. Which has following prototype
• void print_array(int *arr, int max);

Insertion sort program

#include <stdio.h>

#define NUM_ELE(a) sizeof(a)/sizeof(a[0])

int sort_insert(int *, int);
void print_array(int *, int);


int main()
{
   int a[] = {4, 5, 1, 2};

   printf("Unsorted Array is - ");
   print_array(a, NUM_ELE(a));
   printf("\n");

   sort_insert(a, NUM_ELE(a));
   printf("Sorted Array is - ");
   print_array(a, NUM_ELE(a));
   printf("\n");
}
int sort_insert(int *arr, int max)
{
   int idx, right_card, s_idx;

   for(idx = 1; idx < max; idx++) {                                          
      right_card = arr[idx];
      s_idx = idx - 1;
      while(s_idx >= 0 && arr[s_idx] > right_card){
         arr[s_idx + 1] = arr[s_idx];
         s_idx --;
      }
      arr[s_idx + 1] = right_card;
   }
   return 0;
}
void print_array(int *arr, int n)
{
   int i;
   for(i = 0; i < n; i++) {
      printf(" %d", arr[i]);
   }
}

Output of the above program is 

Unsorted Array is -  4 5 1 2
Sorted Array is -  1 2 4 5

Links

Next Article - C Programming Challenge #03: Sort - selection
Previous Article - C Programming Challenge #01: Pascals Traingle
All Article - C Programming Challenge