El algoritmo de clasificación de selección mantiene dos partes.
- La primera parte que ya está ordenada.
- La segunda parte aún no se ha ordenado.
El algoritmo funciona encontrando repetidamente el elemento mínimo (considerando el orden ascendente) de la parte no ordenada y colocándolo al final de la parte ordenada.
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
Ya hemos discutido la clasificación de selección iterativa . En este artículo se discute el enfoque recursivo. La idea de una solución recursiva es incrementar uno por uno la parte ordenada y llamar recursivamente a la parte restante (aún por ordenar).
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 nd 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
Producción:
0 1 2 3 5 7
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar : O(n)
Este artículo es una contribución de Sahil Rajput . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA