Skip to main content

Recursive selection sort

Recursive selection sort is a variant of the selection sort algorithm that uses recursion to sort an array of elements in ascending or descending order.

In the recursive selection sort algorithm, the input array is repeatedly divided into two parts: the first part contains the sorted elements, and the second part contains the unsorted elements. The algorithm recursively sorts the unsorted part by finding the minimum or maximum element and swapping it with the first element of the unsorted part.

This process is repeated until the entire array is sorted. The recursive nature of the algorithm means that each recursive call sorts a smaller sub-array until the sub-array is of size one, which is already sorted by definition.

Recursive selection sort has the same time complexity as the standard selection sort algorithm, which is O(n^2), where n is the number of elements in the input array. However, recursive selection sort can be easier to implement and understand than the iterative version of selection sort.

Program Solution

//C Program
//Recursive selection 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 selection sort in given array
void selection_sort(int record[], int start, int size)
{
	if (start >= size)
	{
		return;
	}
	int location = start;
	//Loop which is iterating array elements from given location to end
	for (int i = start + 1; i < size; ++i)
	{
		if (record[location] > record[i])
		{
			//When get a new small element
			//Get index location
			location = i;
		}
	}
	if (location != start)
	{
		//When need to swap elements
		//Move smallest element at beginning of given start location
		int temp = record[start];
		record[start] = record[location];
		record[location] = temp;
	}
	//Recursive executing the selection sort process
	selection_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);
	selection_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 selection sort
class SelectionSort
{
	public:
		//Display array elements
		void display(int record[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << record[i] << " ";
			}
			cout << "\n";
		}
	//Perform selection sort in given array
	void selection_sort(int record[], int start, int size)
	{
		if (start >= size)
		{
			return;
		}
		int location = start;
		//Loop which is iterating array elements from given location to end
		for (int i = start + 1; i < size; ++i)
		{
			if (record[location] > record[i])
			{
				//When get a new small element
				//Get index location
				location = i;
			}
		}
		if (location != start)
		{
			//When need to swap elements
			//Move smallest element at beginning of given start location
			int temp = record[start];
			record[start] = record[location];
			record[location] = temp;
		}
		//Recursive executing the selection sort process
		this->selection_sort(record, start + 1, size);
	}
};
int main()
{
	SelectionSort obj = SelectionSort();
	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.selection_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 selection sort

class SelectionSort
{
	//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 selection sort in given array
	public void selection_sort(int[] record, int start, int size)
	{
		if (start >= size)
		{
			return;
		}
		int location = start;
		//Loop which is iterating array elements from given location to end
		for (int i = start + 1; i < size; ++i)
		{
			if (record[location] > record[i])
			{
				//When get a new small element
				//Get index location
				location = i;
			}
		}
		if (location != start)
		{
			//When need to swap elements
			//Move smallest element at beginning of given start location
			int temp = record[start];
			record[start] = record[location];
			record[location] = temp;
		}
		//Recursive executing the selection sort process
		selection_sort(record, start + 1, size);
	}
	public static void main(String[] args)
	{
		SelectionSort obj = new SelectionSort();
		//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.selection_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 selection sort
class SelectionSort
{
	//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 selection sort in given array
	public void selection_sort(int[] record, int start, int size)
	{
		if (start >= size)
		{
			return;
		}
		int location = start;
		//Loop which is iterating array elements from given location to end
		for (int i = start + 1; i < size; ++i)
		{
			if (record[location] > record[i])
			{
				//When get a new small element
				//Get index location
				location = i;
			}
		}
		if (location != start)
		{
			//When need to swap elements
			//Move smallest element at beginning of given start location
			int temp = record[start];
			record[start] = record[location];
			record[location] = temp;
		}
		//Recursive executing the selection sort process
		selection_sort(record, start + 1, size);
	}
	public static void Main(String[] args)
	{
		SelectionSort obj = new SelectionSort();
		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.selection_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 selection sort
class SelectionSort
{
	//Display array elements
	public	function display( & $record, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $record[$i] ." ";
		}
		echo "\n";
	}
	//Perform selection sort in given array
	public	function selection_sort( & $record, $start, $size)
	{
		if ($start >= $size)
		{
			return;
		}
		$location = $start;
		//Loop which is iterating array elements from given location to end
		for ($i = $start + 1; $i < $size; ++$i)
		{
			if ($record[$location] > $record[$i])
			{
				//When get a new small element
				//Get index location
				$location = $i;
			}
		}
		if ($location != $start)
		{
			//When need to swap elements
			//Move smallest element at beginning of given start location
			$temp = $record[$start];
			$record[$start] = $record[$location];
			$record[$location] = $temp;
		}
		//Recursive executing the selection sort process
		$this->selection_sort($record, $start + 1, $size);
	}
}

function main()
{
	$obj = new SelectionSort();
	//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->selection_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 selection sort
class SelectionSort
{
	//Display array elements
	display(record, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + record[i] + " ");
		}
		process.stdout.write("\n");
	}
	//Perform selection sort in given array
	selection_sort(record, start, size)
	{
		if (start >= size)
		{
			return;
		}
		var location = start;
		//Loop which is iterating array elements from given location to end
		for (var i = start + 1; i < size; ++i)
		{
			if (record[location] > record[i])
			{
				//When get a new small element
				//Get index location
				location = i;
			}
		}
		if (location != start)
		{
			//When need to swap elements
			//Move smallest element at beginning of given start location
			var temp = record[start];
			record[start] = record[location];
			record[location] = temp;
		}
		//Recursive executing the selection sort process
		this.selection_sort(record, start + 1, size);
	}
}

function main()
{
	var obj = new SelectionSort();
	//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.selection_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 selection sort
class SelectionSort :
	# Display array elements
	def display(self, record, size) :
		i = 0
		while (i < size) :
			print(" ", record[i] ,end = " ")
			i += 1
		
		print(end = "\n")
	
	# Perform selection sort in given array
	def selection_sort(self, record, start, size) :
		if (start >= size) :
			return
		
		location = start
		i = start + 1
		# Loop which is iterating array elements from given location to end
		while (i < size) :
			if (record[location] > record[i]) :
				# When get a new small element
				# Get index location
				location = i
			
			i += 1
		
		if (location != start) :
			# When need to swap elements
			# Move smallest element at beginning of given start location
			temp = record[start]
			record[start] = record[location]
			record[location] = temp
		
		# Recursive executing the selection sort process
		self.selection_sort(record, start + 1, size)
	

def main() :
	obj = SelectionSort()
	# 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.selection_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 selection sort
class SelectionSort

	# Display array elements
	def display(record, size)
	
		i = 0
		while (i < size)
		
			print(" ", record[i] ," ")
			i += 1
		end
		print("\n")
	end
	# Perform selection sort in given array
	def selection_sort(record, start, size)
	
		if (start >= size)
		
			return
		end
		location = start
		i = start + 1
		# Loop which is iterating array elements from given location to end
		while (i < size)
		
			if (record[location] > record[i])
			
				# When get a new small element
				# Get index location
				location = i
			end
			i += 1
		end
		if (location != start)
		
			# When need to swap elements
			# Move smallest element at beginning of given start location
			temp = record[start]
			record[start] = record[location]
			record[location] = temp
		end
		# Recursive executing the selection sort process
		self.selection_sort(record, start + 1, size)
	end
end
def main()

	obj = SelectionSort.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.selection_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 selection sort
class SelectionSort
{
	//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 selection sort in given array
	def selection_sort(record: Array[Int], start: Int, size: Int): Unit = {
		if (start >= size)
		{
			return;
		}
		var location: Int = start;
		var i: Int = start + 1;
		//Loop which is iterating array elements from given location to end
		while (i < size)
		{
			if (record(location) > record(i))
			{
				//When get a new small element
				//Get index location
				location = i;
			}
			i += 1;
		}
		if (location != start)
		{
			//When need to swap elements
			//Move smallest element at beginning of given start location
			var temp: Int = record(start);
			record(start) = record(location);
			record(location) = temp;
		}
		//Recursive executing the selection sort process
		selection_sort(record, start + 1, size);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: SelectionSort = new SelectionSort();
		//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.selection_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 selection sort
class SelectionSort
{
	//Display array elements
	func display(_ record: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", record[i] ," ", terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	//Perform selection sort in given array
	func selection_sort(_ record: inout[Int], _ start: Int, _ size: Int)
	{
		if (start >= size)
		{
			return;
		}
		var location: Int = start;
		var i: Int = start + 1;
		//Loop which is iterating array elements from given location to end
		while (i < size)
		{
			if (record[location] > record[i])
			{
				//When get a new small element
				//Get index location
				location = i;
			}
			i += 1;
		}
		if (location != start)
		{
			//When need to swap elements
			//Move smallest element at beginning of given start location
			let temp: Int = record[start];
			record[start] = record[location];
			record[location] = temp;
		}
		//Recursive executing the selection sort process
		self.selection_sort(&record, start + 1, size);
	}
}
func main()
{
	let obj: SelectionSort = SelectionSort();
	//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.selection_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
Last updated on by Kalkicode




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