Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Below is an iterative algorithm for insertion sort
Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
a) Pick element arr[i] and insert
it into sorted sequence arr[0..i-1]
Example:
Refer Insertion Sort for more details.
How to implement it recursively?
Recursive Insertion Sort has no performance/implementation advantages, but can be a good question to check one’s understanding of Insertion Sort and recursion.
If we take a closer look at Insertion Sort algorithm, we keep processed elements sorted and insert new elements one by one in the sorted array.
Recursion Idea.
- Base Case: If array size is 1 or smaller, return.
- Recursively sort first n-1 elements.
- Insert last element at its correct position in sorted array.
Below is implementation of above idea.
C++
// Recursive C++ program for insertion sort #include <iostream> using namespace std; // Recursive function to sort an array using // insertion sort void insertionSortRecursive(int arr[], int n) { // Base case if (n <= 1) return; // Sort first n-1 elements insertionSortRecursive( arr, n-1 ); // Insert last element at its correct position // in sorted array. int last = arr[n-1]; int j = n-2; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > last) { arr[j+1] = arr[j]; j--; } arr[j+1] = last; } // A utility function to print an array of size n void printArray(int arr[], int n) { for (int i=0; i < n; i++) cout << arr[i] <<" "; } /* Driver program to test insertion sort */int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr)/sizeof(arr[0]); insertionSortRecursive(arr, n); printArray(arr, n); return 0; } |
C
#include <stdio.h> // Recursive function to sort an array using // insertion sort void insertionSortRecursive(int arr[], int n) { // Base case if (n <= 1) return; // Sort first n-1 elements insertionSortRecursive(arr, n - 1); // Insert last element at its correct position // in sorted array. int last = arr[n - 1]; int j = n - 2; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > last) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = last; } // A utility function to print an array of size n void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } /* Driver program to test insertion sort */int main() { int arr[] = { 12, 11, 13, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); insertionSortRecursive(arr, n); printArray(arr, n); return 0; } // This code is contributed by pariveshsrivastava1093 |
Java
// Recursive Java program for insertion sort import java.util.Arrays; public class GFG { // Recursive function to sort an array using // insertion sort static void insertionSortRecursive(int arr[], int n) { // Base case if (n <= 1) return; // Sort first n-1 elements insertionSortRecursive( arr, n-1 ); // Insert last element at its correct position // in sorted array. int last = arr[n-1]; int j = n-2; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > last) { arr[j+1] = arr[j]; j--; } arr[j+1] = last; } // Driver Method public static void main(String[] args) { int arr[] = {12, 11, 13, 5, 6}; insertionSortRecursive(arr, arr.length); System.out.println(Arrays.toString(arr)); } } |
Python3
# Recursive Python program for insertion sort # Recursive function to sort an array using insertion sort def insertionSortRecursive(arr,n): # base case if n<=1: return # Sort first n-1 elements insertionSortRecursive(arr,n-1) '''Insert last element at its correct position in sorted array.''' last = arr[n-1] j = n-2 # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position while (j>=0 and arr[j]>last): arr[j+1] = arr[j] j = j-1 arr[j+1]=last # A utility function to print an array of size n def printArray(arr,n): for i in range(n): print(arr[i],end=" ") # Driver program to test insertion sort arr = [12,11,13,5,6] n = len(arr) insertionSortRecursive(arr, n) printArray(arr, n) # Contributed by Harsh Valecha |
C#
// Recursive C# program // for insertion sort using System; class GFG { // Recursive function to sort // an array using insertion sort static void insertionSortRecursive(int []arr, int n) { // Base case if (n <= 1) return; // Sort first n-1 elements insertionSortRecursive(arr, n - 1); // Insert last element at // its correct position // in sorted array. int last = arr[n - 1]; int j = n - 2; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > last) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = last; } //Driver Code static void Main() { int []arr = {12, 11, 13, 5, 6}; insertionSortRecursive(arr, arr.Length); for(int i = 0; i < arr.Length; i++) Console.Write(arr[i] + " "); } } // This code is contributed by Sam007 |
PHP
<?php // Recursive PHP program for insertion sort // Recursive function to sort an // array using insertion sort function insertionSortRecursive(&$arr, $n) { // Base case if ($n <= 1) return; // Sort first n-1 elements insertionSortRecursive($arr, $n - 1); // Insert last element at its correct // position in sorted array. $last = $arr[$n - 1]; $j = $n - 2; // Move elements of arr[0..i-1], that are // greater than key, to one position ahead // of their current position while ($j >= 0 && $arr[$j] > $last) { $arr[$j + 1] = $arr[$j]; $j--; } $arr[$j + 1] = $last; } // A utility function to // print an array of size n function printArray(&$arr, $n) { for ($i = 0; $i < $n; $i++) echo $arr[$i]." "; } // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSortRecursive($arr, $n); printArray($arr, $n); // This code is contributed by ChitraNayal. ?> |
Javascript
<script> // Recursive Javascript program for // insertion sort // Recursive function to sort an //array using insertion sort function insertionSortRecursive(arr,n) { // Base case if (n <= 1) return; // Sort first n-1 elements insertionSortRecursive( arr, n-1 ); // Insert last element at its // correct position in sorted array. let last = arr[n-1]; let j = n-2; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > last) { arr[j+1] = arr[j]; j--; } arr[j+1] = last; } // Driver Method let arr=[12, 11, 13, 5, 6]; insertionSortRecursive(arr, arr.length); for(let i=0;i<arr.length;i++) { document.write(arr[i]+" "); } // This code is contributed by rag2127 </script> |
Output :
5 6 11 12 13
Time Complexity: O(n2)
Auxiliary Space: O(n)
This article is contributed by Sahil Chhabra. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
