Insertion sort using recursion

 Problem statement:- Program to Implement Insertion sort using recursion.

Data requirement:-

   Input Data:-n, arr

  Output Data:-String Output

Program in C

Here is the source code of the C Program to Implement Insertion sort using recursion.

Code:

#include<stdio.h>
void InsertionSort(int arr[], int n)
{
    if(n<=1)
    return;
    InsertionSort(arr, n-1);
    int temp = arr[n-1];
    int in = n-2;
    while(in>=0 && arr[in]>temp)
        {
            arr[in+1] = arr[in];
            in--;
        }
        arr[in+1] = temp;
    }
int main()
{
    int size;
    printf("Enter the size of the array:");
    scanf("%d",&size);
    int arr[size],i;
    printf("Enter the element of the array:");
    for(i=0;i<size;i++)
        scanf("%d",&arr[i]);

    printf("Before Sorting Array Element are: ");
    for(i=0;i<size;i++)
        printf("%d ",arr[i]);
       InsertionSort(arr, size);
        printf("\nAfter Sorting Array Element are: ");
        for(i=0;i<size;i++)
        printf("%d ",arr[i]);
}

Input/Output:

Enter the size of the array:5

Enter the element of the array:7 8 9 3 6

Before Sorting Array Element are: 7 8 9 3 6

After Sorting Array Element are: 3 6 7 8 9

Program in C++

Here is the source code of the C++ Program to Implement Insertion sort using recursion.

Code:

#include<iostream>

using namespace std;

void InsertionSort(int arr[], int n)

{

    if(n<=1)

    return;

    InsertionSort(arr, n-1);

    int temp = arr[n-1];

    int in = n-2;

    while(in>=0 && arr[in]>temp)

        {

            arr[in+1] = arr[in];

            in--;

        }

        arr[in+1] = temp;

    }

int main()

{

    int size;

    cout<<"Enter the size of the array:";

    cin>>size;

    int arr[size],i;

    cout<<"Enter the element of the array:";

    for(i=0;i<size;i++)

       cin>>arr[i];

    cout<<"Before Sorting Array Element are:";

    for(i=0;i<size;i++)

    cout<<arr[i]<<" ";

    InsertionSort(arr, size);

    cout<<"\nAfter Sorting Array Element are: ";

    for(i=0;i<size;i++)

    cout<<arr[i]<<" ";

}

Input/Output:

Enter the size of the array:6

Enter the element of the array:11 2 5 33 6 7

Before Sorting Array Element are:11 2 5 33 6 7

After Sorting Array Element are: 2 5 6 7 11 33

Program in Java

Here is the source code of the Java Program to Implement Insertion sort using recursion.

Code:

import java.util.Scanner;

public class InsertionSortArray {

static void InsertionSort(int arr[], int n)

{

    if(n<=1)

    return;

    InsertionSort(arr, n-1);

    int temp = arr[n-1];

    int in = n-2;

    while(in>=0 && arr[in]>temp)

        {

            arr[in+1] = arr[in];

            in--;

        }

        arr[in+1] = temp;

    }

public static void main(String[] args) {

Scanner cs=new Scanner(System.in);

int n,i;

System.out.println("Enter your Array Size:");

n=cs.nextInt();

int arr[]=new int[n];

System.out.println("Enter the Array Element:");

for(i=0;i<n;i++)

{

arr[i]=cs.nextInt();

}

System.out.print("Before Sorting Array Element are: ");

  for(i=0;i<n;i++)

  System.out.print(arr[i]+" ");

  InsertionSort(arr, n);

  System.out.print("\nAfter Sorting Array Element are: ");

   for(i=0;i<n;i++)

      System.out.print(arr[i]+" ");

cs.close();

}

}

Input/Output:

Enter your Array Size:

4

Enter the Array Element:

3 9 5 6

Before Sorting Array Element are: 3 9 5 6 

After Sorting Array Element are: 3 5 6 9 

Program in Python

Here is the source code of the Python program to Implement Insertion sort using recursion.

Code:

def InsertionSort(arr,n):

    if(n<=1):

        return

    InsertionSort(arr, n-1)

    temp = arr[n - 1]

    i = n - 2

    while (i >= 0 and arr[i] > temp):

        arr[ i +1] = arr[ i]

        i=i-1

    arr[i+1] = temp

arr=[]

n = int(input("Enter the size of the array: "))

print("Enter the Element of the array:")

for i in range(0,n):

    num = int(input())

    arr.append(num)

print("Before Sorting Array Element are: ",arr)

InsertionSort(arr, n)

print("After Sorting Array Elements are:",arr)

Input/Output:

Enter the size of the array: 3

Enter the Element of the array:

4

7

3

Before Sorting Array Element are:  [4, 7, 3]

After Sorting Array Elements are: [3, 4, 7]

Most Recommend Questions:-

•  Write a Program to Sort array in descending order using recursion.

• Write a Program to  Implement Bubble sort using recursion.

 

• Write a Program to Sort array in ascending order using recursion.

• Quick Sort

• Merge Sort

More Questions:-

C/C++/Java/Python Practice Question

Sorting Programming Question and Solutions