C program to implement Recursive Insertion Sort

Here, we are implementing C program to sort array elements using the recursive insertion sort.
Submitted by Sneha Dujaniya, on June 19, 2020

The only difference between Insertion sort and Recursive Insertion Sort is that in the Recursive method, we start from placing the last element in its correct position in the sorted array instead of starting from the first.

Here, I will only be showing the C implementation of the sort as I have explained the basic theory in my previous article.

Recursive Insertion Sort Implementation:

#include <stdio.h>

void rec_insertion(int arr[], int n)
{
    // When the elements are all over
    if (n <= 1)
        return;

    // sorting n-1 elements
    rec_insertion(arr, n - 1);

    int last = arr[n - 1];
    int j = n - 2;

    while (j >= 0 && last < arr[j]) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;

    printf("\nAfter performing Insertion sort:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

int main()
{
    int arr[] = { 10, 14, 3, 8, 5, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);

    rec_insertion(arr, n);

    return 0;
}

Output:

After performing Insertion sort:
10 14
After performing Insertion sort:
3 10 14
After performing Insertion sort:
3 8 10 14
After performing Insertion sort:
3 5 8 10 14
After performing Insertion sort:
3 5 8 10 12 14

This output shows the array after each ith iteration. Feel free to ask your doubts.






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.