Recursive Selection Sort
The Selection Sort algorithm sorts maintain two parts.
- The first part that is already sorted
- The second part is yet to be sorted.
The algorithm works by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the end of the sorted part.
arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 25 64
We have already discussed Iterative Selection Sort. In this article recursive approach is discussed. The idea of a recursive solution is to one by one increment sorted part and recursively call for the remaining (yet to be sorted) part.
C++
// Recursive C++ program to sort an array // using selection sort #include <iostream> using namespace std; // Return minimum index int minIndex( int a[], int i, int j) { if (i == j) return i; // Find minimum of remaining elements int k = minIndex(a, i + 1, j); // Return minimum of current and remaining. return (a[i] < a[k])? i : k; } // Recursive selection sort. n is size of a[] and index // is index of starting element. void recurSelectionSort( int a[], int n, int index = 0) { // Return when starting and size are same if (index == n) return ; // calling minimum index function for minimum index int k = minIndex(a, index, n-1); // Swapping when index and minimum index are not same if (k != index) swap(a[k], a[index]); // Recursively calling selection sort function recurSelectionSort(a, n, index + 1); } // Driver code int main() { int arr[] = {3, 1, 5, 2, 7, 0}; int n = sizeof (arr)/ sizeof (arr[0]); // Calling function recurSelectionSort(arr, n); //printing sorted array for ( int i = 0; i<n ; i++) cout << arr[i] << " " ; cout << endl; return 0; } |
Java
// Recursive Java program to sort an array // using selection sort class Test { // Return minimum index static int minIndex( int a[], int i, int j) { if (i == j) return i; // Find minimum of remaining elements int k = minIndex(a, i + 1 , j); // Return minimum of current and remaining. return (a[i] < a[k])? i : k; } // Recursive selection sort. n is size of a[] and index // is index of starting element. static void recurSelectionSort( int a[], int n, int index) { // Return when starting and size are same if (index == n) return ; // calling minimum index function for minimum index int k = minIndex(a, index, n- 1 ); // Swapping when index and minimum index are not same if (k != index){ // swap int temp = a[k]; a[k] = a[index]; a[index] = temp; } // Recursively calling selection sort function recurSelectionSort(a, n, index + 1 ); } // Driver method public static void main(String args[]) { int arr[] = { 3 , 1 , 5 , 2 , 7 , 0 }; // Calling function recurSelectionSort(arr, arr.length, 0 ); //printing sorted array for ( int i = 0 ; i< arr.length; i++) System.out.print(arr[i] + " " ); } } |
Python3
# Recursive Python3 code to sort # an array using selection sort # Return minimum index def minIndex( a , i , j ): if i = = j: return i # Find minimum of remaining elements k = minIndex(a, i + 1 , j) # Return minimum of current # and remaining. return (i if a[i] < a[k] else k) # Recursive selection sort. n is # size of a[] and index is index of # starting element. def recurSelectionSort(a, n, index = 0 ): # Return when starting and # size are same if index = = n: return - 1 # calling minimum index function # for minimum index k = minIndex(a, index, n - 1 ) # Swapping when index and minimum # index are not same if k ! = index: a[k], a[index] = a[index], a[k] # Recursively calling selection # sort function recurSelectionSort(a, n, index + 1 ) # Driver code arr = [ 3 , 1 , 5 , 2 , 7 , 0 ] n = len (arr) # Calling function recurSelectionSort(arr, n) # printing sorted array for i in arr: print (i, end = ' ' ) # This code is contributed by "Sharad_Bhardwaj". |
C#
// Recursive C# program to sort an array // using selection sort using System; class GFG { // Return minimum index static int minIndex( int []a, int i, int j) { if (i == j) return i; // Find minimum of remaining elements int k = minIndex(a, i + 1, j); // Return minimum of current and remaining. return (a[i] < a[k])? i : k; } // Recursive selection sort. n is size of // a[] and index is index of starting element. static void recurSelectionSort( int []a, int n, int index) { // Return when starting and size are same if (index == n) return ; // calling minimum index function // for minimum index int k = minIndex(a, index, n - 1); // Swapping when index and minimum index // are not same if (k != index) { // swap int temp = a[k]; a[k] = a[index]; a[index] = temp; } // Recursively calling selection sort function recurSelectionSort(a, n, index + 1); } // Driver Code public static void Main(String []args) { int []arr = {3, 1, 5, 2, 7, 0}; // Calling function recurSelectionSort(arr, arr.Length, 0); //printing sorted array for ( int i = 0; i< arr.Length; i++) Console.Write(arr[i] + " " ); } } // This code is contributed by Princi Singh |
Javascript
// Recursive JavaScript program to sort an array // using selection sort // Return minimum index function minIndex(a, i, j) { if (i == j) return i; // Find minimum of remaining elements var k = minIndex(a, i + 1, j); // Return minimum of current and remaining. return (a[i] < a[k])? i : k; } // Recursive selection sort. n is size of a[] and index // is index of starting element. function recurSelectionSort(a, n, index = 0) { // Return when starting and size are same if (index == n) return ; // calling minimum index function for minimum index var k = minIndex(a, index, n-1); // Swapping when index and minimum index are not same if (k != index) [a[k], a[index]] = [a[index], a[k]]; // Recursively calling selection sort function recurSelectionSort(a, n, index + 1); } // Driver code var arr = [3, 1, 5, 2, 7, 0]; var n = arr.length; // Calling function recurSelectionSort(arr, n); //printing sorted array console.log(arr.join( ' ' )); |
Output:
0 1 2 3 5 7
Time Complexity: O(n2)
Auxiliary Space: O(n)
Contact Us