C program for recursive insertion sort

Insertion sort is a sorting algorithm that is based on in-place comparison.

This algorithm works by placing an element at a position in a sorted subarray, i.e. the subarray before the element is the sorted subarray.

Algorithm

Step1 - Loop from 1 to n-1 and execute -

Step2 .1 - Select the element at position i, array[i].

Step2.2 - Insert the element into the sorted subarray array[0] at its position arr[i].

Let’s understand the algorithm through an example

Array = [34, 7, 12, 90, 51]

For i = 1, arr[1] = 7, put the position in the subarray arr[0] - arr[1].

[7, 34, 12, 90, 51]

For i = 2, arr[2] = 12, put the position in the subarray arr[0] - arr[2].

[7, 12, 34, 90, 51]

For i = 3, arr[3] = 90, place it in the subarray arr[0] - arr[3].

[7, 12, 34, 90, 51]

For i = 4, arr[4] = 51, place it in the correct position in the subarray arr[0] - arr[4].

[7, 12, 34, 54, 90]

Here we will see how recursive insertion sort works. It works in the opposite way, i.e. we will recursively call the recursiveInsertionSort() function to sort an array of n-1 elements compared to the current iteration. Then in the sorted array returned by the function, we insert the nth element into its position in the sorted array.

The program of recursive insertion sort is as follows:

Example

Demonstration

#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
   if (n <= 1)
      return;
   recursiveInsertionSort( arr, n-1 );
   int nth = arr[n-1];
   int j = n-2;
   while (j >= 0 && arr[j] > nth){
      arr[j+1] = arr[j];
      j--;
   }
   arr[j+1] = nth;
}
int main(){
   int array[] = {34, 7, 12, 90, 51};
   int n = sizeof(array)/sizeof(array[0]);
   printf("Unsorted Array:\t");
      for (int i=0; i < n; i++)
   printf("%d ",array[i]);
      recursiveInsertionSort(array, n);
   printf("</p><p>Sorted Array:\t");
   for (int i=0; i < n; i++)
      printf("%d ",array[i]);
   return 0;
}

Output

Unsorted Array: 34 7 12 90 51
Sorted Array: 7 12 34 51 90

The above is the detailed content of C program for recursive insertion sort. For more information, please follow other related articles on the PHP Chinese website!