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