El algoritmo de clasificación por selección clasifica una array encontrando repetidamente el elemento mínimo (considerando el orden ascendente) de la parte no clasificada y colocándolo al principio. El algoritmo mantiene dos subarreglos en un arreglo dado.
- El subarreglo que ya está ordenado.
- Subarreglo restante que no está ordenado.
En cada iteración del ordenamiento por selección, el elemento mínimo (considerando el orden ascendente) del subarreglo no ordenado se selecciona y se mueve al subarreglo ordenado.
Diagrama de flujo de la clasificación de selección:
¿Cómo funciona la ordenación por selección?
Consideremos la siguiente array como ejemplo: arr[] = {64, 25, 12, 22, 11}
Primer pase:
- Para la primera posición en la array ordenada, toda la array se recorre secuencialmente desde el índice 0 al 4. La primera posición donde se almacena 64 actualmente, después de atravesar toda la array, está claro que 11 es el valor más bajo.
64 25 12 22 11
- Por lo tanto, reemplace 64 con 11. Después de una iteración , 11 , que resulta ser el menor valor en la array, tiende a aparecer en la primera posición de la lista ordenada.
11 25 12 22 64 Segundo pase:
- Para la segunda posición, donde está presente 25, recorra nuevamente el resto de la array de manera secuencial.
11 25 12 22 64
- Después de atravesar, encontramos que 12 es el segundo valor más bajo en la array y debería aparecer en el segundo lugar de la array, por lo tanto, intercambie estos valores.
11 12 25 22 64 Tercer Pase:
- Ahora, para el tercer lugar, donde 25 está presente nuevamente, recorra el resto de la array y encuentre el tercer valor menor presente en la array.
11 12 25 22 64
- Durante el recorrido, 22 resultó ser el tercer valor más bajo y debería aparecer en el tercer lugar de la array, por lo tanto, intercambie 22 con el elemento presente en la tercera posición.
11 12 22 25 64 Cuarto pase:
- De manera similar, para la cuarta posición, recorra el resto de la array y encuentre el cuarto elemento menos en la array
- Como 25 es el cuarto valor más bajo, por lo tanto, se colocará en la cuarta posición.
11 12 22 25 64 Quinto Pase:
- Por fin, el valor más grande presente en la array se coloca automáticamente en la última posición de la array.
- La array resultante es la array ordenada.
11 12 22 25 64
C++
// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;
//Swap function
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of
// unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in
// unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element
// with the first element
swap(&arr[min_idx], &arr[i]);
}
}
//Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program for implementation of selection sort
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Python3
# Python program for implementation of Selection
# Sort
import sys
A = [64, 25, 12, 22, 11]
# Traverse through all array elements
for i in range(len(A)):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# Swap the found minimum element with
# the first element
A[i], A[min_idx] = A[min_idx], A[i]
# Driver code to test above
print ("Sorted array")
for i in range(len(A)):
print("%d" %A[i],end=" ")
Java
// Java program for implementation of Selection Sort
class SelectionSort
{
void sort(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Prints the array
void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver code to test above
public static void main(String args[])
{
SelectionSort ob = new SelectionSort();
int arr[] = {64,25,12,22,11};
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
/* This code is contributed by Rajat Mishra*/
C#
// C# program for implementation
// of Selection Sort
using System;
class GFG
{
static void sort(int []arr)
{
int n = arr.Length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Prints the array
static void printArray(int []arr)
{
int n = arr.Length;
for (int i=0; i<n; ++i)
Console.Write(arr[i]+" ");
Console.WriteLine();
}
// Driver code
public static void Main()
{
int []arr = {64,25,12,22,11};
sort(arr);
Console.WriteLine("Sorted array");
printArray(arr);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program for implementation
// of selection sort
function selection_sort(&$arr, $n)
{
for($i = 0; $i < $n ; $i++)
{
$low = $i;
for($j = $i + 1; $j < $n ; $j++)
{
if ($arr[$j] < $arr[$low])
{
$low = $j;
}
}
// swap the minimum value to $ith node
if ($arr[$i] > $arr[$low])
{
$tmp = $arr[$i];
$arr[$i] = $arr[$low];
$arr[$low] = $tmp;
}
}
}
// Driver Code
$arr = array(64, 25, 12, 22, 11);
$len = count($arr);
selection_sort($arr, $len);
echo "Sorted array : \n";
for ($i = 0; $i < $len; $i++)
echo $arr[$i] . " ";
// This code is contributed
// by Deepika Gupta.
?>
Javascript
<script>
// Javascript program for implementation of selection sort
function swap(arr,xp, yp)
{
var temp = arr[xp];
arr[xp] = arr[yp];
arr[yp] = temp;
}
function selectionSort(arr, n)
{
var i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(arr,min_idx, i);
}
}
function printArray( arr, size)
{
var i;
for (i = 0; i < size; i++)
document.write(arr[i] + " ");
document.write(" <br>");
}
var arr = [64, 25, 12, 22, 11];
var n = 5;
selectionSort(arr, n);
document.write("Sorted array: <br>");
printArray(arr, n);
// This code is contributed by akshitsaxenaa09.
</script>
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