Recursive insertion sort
Recursive insertion sort is a variant of the insertion sort algorithm that uses recursion to sort an array or list of elements in ascending or descending order. In this algorithm, the base case is an array of one or fewer elements, which is already considered sorted. For arrays with two or more elements, the algorithm divides the array into two parts: a sorted subarray and an unsorted subarray.
The algorithm then recursively sorts the unsorted subarray by calling itself on the subarray, until the base case is reached. Once the base case is reached, the sorted subarray is merged with the sorted subarray from the recursive call to produce the final sorted array.
The basic idea of insertion sort is to iterate through the array from left to right, and for each element, insert it into its correct position in the sorted subarray to its left. The same idea is applied in recursive insertion sort, but with the added recursion.
Program Solution
//C Program
//Recursive insertion sort
#include <stdio.h>
//Display array elements
void display(int record[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", record[i]);
}
printf("\n");
}
//Perform insertion sort in given array
void insertion_sort(int record[], int start, int size)
{
if (start >= size)
{
return;
}
int location = start - 1;
int temp = 0;
while (location >= 0 && record[location + 1] < record[location])
{
//when need to swapping the two consecutive elements
temp = record[location + 1];
record[location + 1] = record[location];
record[location] = temp;
//reduce index location
location = location - 1;
}
//Recursive executing the insertion sort process
insertion_sort(record, start + 1, size);
}
int main()
{
//Assume given array elements
int record[] = {
2 , 8 , 1 , -7 , 5 , 0 , 11 , 9 , 3 , 7 , 2
};
//Get the size of array
int size = sizeof(record) / sizeof(record[0]);
//Before sort
display(record, size);
insertion_sort(record, 0, size);
//After sort
display(record, size);
return 0;
}
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
//Include header file
#include <iostream>
using namespace std;
//C++ Program
//Recursive insertion sort
class InsertionSort
{
public:
//Display array elements
void display(int record[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << record[i] << " ";
}
cout << "\n";
}
//Perform insertion sort in given array
void insertion_sort(int record[], int start, int size)
{
if (start >= size)
{
return;
}
int location = start - 1;
int temp = 0;
while (location >= 0 && record[location + 1] < record[location])
{
//when need to swapping the two consecutive elements
temp = record[location + 1];
record[location + 1] = record[location];
record[location] = temp;
//reduce index location
location = location - 1;
}
//Recursive executing the insertion sort process
this->insertion_sort(record, start + 1, size);
}
};
int main()
{
InsertionSort obj = InsertionSort();
int record[] = {
2 , 8 , 1 , -7 , 5 , 0 , 11 , 9 , 3 , 7 , 2
};
//Get the size of array
int size = sizeof(record) / sizeof(record[0]);
//Before sort
obj.display(record, size);
obj.insertion_sort(record, 0, size);
//After sort
obj.display(record, size);
return 0;
}
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
//Java Program
//Recursive insertion sort
class InsertionSort
{
//Display array elements
public void display(int[] record, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + record[i] + " ");
}
System.out.print("\n");
}
//Perform insertion sort in given array
public void insertion_sort(int[] record, int start, int size)
{
if (start >= size)
{
return;
}
int location = start - 1;
int temp = 0;
while (location >= 0 && record[location + 1] < record[location])
{
//when need to swapping the two consecutive elements
temp = record[location + 1];
record[location + 1] = record[location];
record[location] = temp;
//reduce index location
location = location - 1;
}
//Recursive executing the insertion sort process
insertion_sort(record, start + 1, size);
}
public static void main(String[] args)
{
InsertionSort obj = new InsertionSort();
//Assume given array elements
int[] record = {
2 , 8 , 1 , -7 , 5 , 0 , 11 , 9 , 3 , 7 , 2
};
//Get the size of array
int size = record.length;
//Before sort
obj.display(record, size);
obj.insertion_sort(record, 0, size);
//After sort
obj.display(record, size);
}
}
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
//Include namespace system
using System;
//C# Program
//Recursive insertion sort
class InsertionSort
{
//Display array elements
public void display(int[] record, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + record[i] + " ");
}
Console.Write("\n");
}
//Perform insertion sort in given array
public void insertion_sort(int[] record, int start, int size)
{
if (start >= size)
{
return;
}
int location = start - 1;
int temp = 0;
while (location >= 0 && record[location + 1] < record[location])
{
//when need to swapping the two consecutive elements
temp = record[location + 1];
record[location + 1] = record[location];
record[location] = temp;
//reduce index location
location = location - 1;
}
//Recursive executing the insertion sort process
insertion_sort(record, start + 1, size);
}
public static void Main(String[] args)
{
InsertionSort obj = new InsertionSort();
int[] record = {
2 , 8 , 1 , -7 , 5 , 0 , 11 , 9 , 3 , 7 , 2
};
//Get the size of array
int size = record.Length;
//Before sort
obj.display(record, size);
obj.insertion_sort(record, 0, size);
//After sort
obj.display(record, size);
}
}
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
<?php
//Php Program
//Recursive insertion sort
class InsertionSort
{
//Display array elements
public function display( & $record, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $record[$i] ." ";
}
echo "\n";
}
//Perform insertion sort in given array
public function insertion_sort( & $record, $start, $size)
{
if ($start >= $size)
{
return;
}
$location = $start - 1;
$temp = 0;
while ($location >= 0 && $record[$location + 1] < $record[$location])
{
//when need to swapping the two consecutive elements
$temp = $record[$location + 1];
$record[$location + 1] = $record[$location];
$record[$location] = $temp;
//reduce index location
$location = $location - 1;
}
//Recursive executing the insertion sort process
$this->insertion_sort($record, $start + 1, $size);
}
}
function main()
{
$obj = new InsertionSort();
//Assume given array elements
$record = array(2, 8, 1, -7, 5, 0, 11, 9, 3, 7, 2);
//Get the size of array
$size = count($record);
//Before sort
$obj->display($record, $size);
$obj->insertion_sort($record, 0, $size);
//After sort
$obj->display($record, $size);
}
main();
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
//Node Js Program
//Recursive insertion sort
class InsertionSort
{
//Display array elements
display(record, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + record[i] + " ");
}
process.stdout.write("\n");
}
//Perform insertion sort in given array
insertion_sort(record, start, size)
{
if (start >= size)
{
return;
}
var location = start - 1;
var temp = 0;
while (location >= 0 && record[location + 1] < record[location])
{
//when need to swapping the two consecutive elements
temp = record[location + 1];
record[location + 1] = record[location];
record[location] = temp;
//reduce index location
location = location - 1;
}
//Recursive executing the insertion sort process
this.insertion_sort(record, start + 1, size);
}
}
function main()
{
var obj = new InsertionSort();
//Assume given array elements
var record = [2, 8, 1, -7, 5, 0, 11, 9, 3, 7, 2];
//Get the size of array
var size = record.length;
//Before sort
obj.display(record, size);
obj.insertion_sort(record, 0, size);
//After sort
obj.display(record, size);
}
main();
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
# Python 3 Program
# Recursive insertion sort
class InsertionSort :
# Display array elements
def display(self, record, size) :
i = 0
while (i < size) :
print(" ", record[i] ," ", end = "")
i += 1
print("\n", end = "")
# Perform insertion sort in given array
def insertion_sort(self, record, start, size) :
if (start >= size) :
return
location = start - 1
temp = 0
while (location >= 0 and record[location + 1] < record[location]) :
# when need to swapping the two consecutive elements
temp = record[location + 1]
record[location + 1] = record[location]
record[location] = temp
# reduce index location
location = location - 1
# Recursive executing the insertion sort process
self.insertion_sort(record, start + 1, size)
def main() :
obj = InsertionSort()
# Assume given array elements
record = [2, 8, 1, -7, 5, 0, 11, 9, 3, 7, 2]
# Get the size of array
size = len(record)
# Before sort
obj.display(record, size)
obj.insertion_sort(record, 0, size)
# After sort
obj.display(record, size)
if __name__ == "__main__": main()
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
# Ruby Program
# Recursive insertion sort
class InsertionSort
# Display array elements
def display(record, size)
i = 0
while (i < size)
print(" ", record[i] ," ")
i += 1
end
print("\n")
end
# Perform insertion sort in given array
def insertion_sort(record, start, size)
if (start >= size)
return
end
location = start - 1
temp = 0
while (location >= 0 && record[location + 1] < record[location])
# when need to swapping the two consecutive elements
temp = record[location + 1]
record[location + 1] = record[location]
record[location] = temp
# reduce index location
location = location - 1
end
# Recursive executing the insertion sort process
self.insertion_sort(record, start + 1, size)
end
end
def main()
obj = InsertionSort.new()
# Assume given array elements
record = [2, 8, 1, -7, 5, 0, 11, 9, 3, 7, 2]
# Get the size of array
size = record.length
# Before sort
obj.display(record, size)
obj.insertion_sort(record, 0, size)
# After sort
obj.display(record, size)
end
main()
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
//Scala Program
//Recursive insertion sort
class InsertionSort
{
//Display array elements
def display(record: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + record(i) + " ");
i += 1;
}
print("\n");
}
//Perform insertion sort in given array
def insertion_sort(record: Array[Int], start: Int, size: Int): Unit = {
if (start >= size)
{
return;
}
var location: Int = start - 1;
var temp: Int = 0;
while (location >= 0 && record(location + 1) < record(location))
{
//when need to swapping the two consecutive elements
temp = record(location + 1);
record(location + 1) = record(location);
record(location) = temp;
//reduce index location
location = location - 1;
}
//Recursive executing the insertion sort process
insertion_sort(record, start + 1, size);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: InsertionSort = new InsertionSort();
//Assume given array elements
var record: Array[Int] = Array(2, 8, 1, -7, 5, 0, 11, 9, 3, 7, 2);
//Get the size of array
var size: Int = record.length;
//Before sort
obj.display(record, size);
obj.insertion_sort(record, 0, size);
//After sort
obj.display(record, size);
}
}
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
//Swift Program
//Recursive insertion sort
class InsertionSort
{
//Display array elements
func display(_ record: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", record[i] ," ", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Perform insertion sort in given array
func insertion_sort(_ record: inout[Int], _ start: Int, _ size: Int)
{
if (start >= size)
{
return;
}
var location: Int = start - 1;
var temp: Int = 0;
while (location >= 0 && record[location + 1] < record[location])
{
//when need to swapping the two consecutive elements
temp = record[location + 1];
record[location + 1] = record[location];
record[location] = temp;
//reduce index location
location = location - 1;
}
//Recursive executing the insertion sort process
self.insertion_sort(&record, start + 1, size);
}
}
func main()
{
let obj: InsertionSort = InsertionSort();
//Assume given array elements
var record: [Int] = [2, 8, 1, -7, 5, 0, 11, 9, 3, 7, 2];
//Get the size of array
let size: Int = record.count;
//Before sort
obj.display(record, size);
obj.insertion_sort(&record, 0, size);
//After sort
obj.display(record, size);
}
main();
Output
2 8 1 -7 5 0 11 9 3 7 2
-7 0 1 2 2 3 5 7 8 9 11
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment