C Programming Challenge #06: Sort - insertion (using recursion)

We have already covered the insertion sort C Programming Challenge #02: Sort - insertion. Challenge is to implement it using recursion.

Recursive definition of insertion sort is

• In order to sort a[0] to a[n] we first sort a[0] to a [n -1] and then insert a[n] into sorted array.
• Trivial solution is when n = 0, no need to sorted. Array of 1 element is always sorted.

Solution would look as follows.

#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 i;
   int a[] = {4, 5, 1, 2};

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

   sort_insert(a, NUM_ELE(a) - 1);

   printf("Sorted Array is - ");
   print_array(a, NUM_ELE(a));
   printf("\n");
}
int sort_insert(int *arr, int n)
{
   int i;
   int cur_card;
   if(n >= 1) {
      /* First sort array from arr[0] to arr[n - 1] */
      sort_insert(arr, n - 1);
      /* Following code is to insert arr[n] 
         into sorted array of arr[0] tp arr[n - 1] */
      cur_card = arr[n];
      i = n - 1;
      while(i >= 0 && arr[i] > cur_card) {
         arr[i + 1] = arr[i];
         i--;
      }
      arr[i + 1] = cur_card;
   }
   return 0;
}
void print_array(int *arr, int n)
{
   int i;
   for(i = 0; i < n; i++) {
      printf(" %d", arr[i]);
   }
}

Output is as expected

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

Links

Next Article - C Programming Challenge #07: Search - binary
Previous Article - C Programming Challenge #05: Sort - merge (without sentinels)
All Article - C Programming Challenge