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
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