**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.

#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 - binaryPrevious Article - C Programming Challenge #05: Sort - merge (without sentinels)

All Article - C Programming Challenge

## No comments :

## Post a Comment