Posted on by Kalkicode
Code Sorting

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

Comment

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





Categories
Relative Post