Selection Sort
Última actualización
El selection sort divide el arreglo en una región ordenada a la izquierda y una región no ordenada a la derecha. En cada pasada recorre la región no ordenada para encontrar el elemento más pequeño y luego lo intercambia a la primera posición no ordenada, aumentando la región ordenada en uno. Pulsa reproducir arriba para ver el recorrido e intercambio, o avanza comparación por comparación.
El selection sort siempre realiza el mismo número de comparaciones sin importar la entrada, pero hace como máximo n-1 intercambios - muchos menos que el bubble sort - lo que importa cuando las escrituras son costosas.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Mejor caso | O(n²) | Las comparaciones ocurren incluso si está ordenado |
| Caso promedio | O(n²) | Orden aleatorio |
| Peor caso | O(n²) | Orden inverso |
| Espacio | O(1) | En el lugar |
| Estable | No | Los intercambios pueden reordenar elementos iguales |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Considera todo el arreglo como no ordenado. |
| 2 | Recorre la región no ordenada para encontrar el elemento mínimo. |
| 3 | Intercambia ese mínimo a la primera posición no ordenada. |
| 4 | Mueve el límite un paso a la derecha (esa posición ya está ordenada). |
| 5 | Repite hasta que solo quede un elemento no ordenado. |
Ejemplo resuelto
Ordenando [5, 2, 4, 1]:
| Pasada | Arreglo | Acción |
|---|---|---|
| Inicio | [5, 2, 4, 1] | Todo el arreglo está no ordenado. |
| 1 | [1, 2, 4, 5] | Recorre [5, 2, 4, 1], el mínimo es 1 en el índice 3; se intercambia con el índice 0. |
| 2 | [1, 2, 4, 5] | Recorre [2, 4, 5], el mínimo es 2 que ya está en el índice 1; se intercambia consigo mismo. |
| 3 | [1, 2, 4, 5] | Recorre [4, 5], el mínimo es 4 que ya está en el índice 2; no hace falta mover nada. |
| Fin | [1, 2, 4, 5] | Solo queda 5, así que ya está en su lugar. |
Cuándo usar selection sort
| Úsalo cuando | Evítalo cuando |
|---|---|
Las escrituras son costosas: hace como máximo n-1 intercambios. | El arreglo es grande: dominan las O(n²) comparaciones. |
| Necesitas un ordenamiento en el lugar simple y fácil de implementar. | Necesitas un ordenamiento estable que conserve el orden de las claves iguales. |
La memoria es limitada: usa solo O(1) de espacio extra. | Los datos están casi ordenados: no puede terminar antes como el insertion sort. |
| El conjunto de datos es diminuto y el rendimiento predecible importa. | Importa el rendimiento: los ordenamientos O(n log n) como quicksort son mucho más rápidos. |
Código de Selection Sort
Una implementación limpia y ejecutable de Selection Sort en Python, JavaScript, Java, C++, C, Pseudocode. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Selection Sort en Python
Python
1def selection_sort(a):2 n = len(a)3 for i in range(n - 1):4 # Find the smallest element in the unsorted tail5 min_idx = i6 for j in range(i + 1, n):7 if a[j] < a[min_idx]:8 min_idx = j9 a[i], a[min_idx] = a[min_idx], a[i]10 return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)Código de Selection Sort en JavaScript
JavaScript
1function selectionSort(a) {2 for (let i = 0; i < a.length - 1; i++) {3 let min = i;4 // Find the smallest element in the unsorted tail5 for (let j = i + 1; j < a.length; j++) {6 if (a[j] < a[min]) min = j;7 }8 if (min !== i) [a[i], a[min]] = [a[min], a[i]];9 }10 return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));Código de Selection Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void selectionSort(int[] arr) {5 for (int i = 0; i < arr.length - 1; i++) {6 int minIndex = i;7 // Find the smallest value in the unsorted part8 for (int j = i + 1; j < arr.length; j++) {9 if (arr[j] < arr[minIndex]) minIndex = j;10 }11 int tmp = arr[i];12 arr[i] = arr[minIndex];13 arr[minIndex] = tmp;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {29, 10, 14, 37, 13, 5};19 System.out.println("Before: " + Arrays.toString(arr));20 selectionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Código de Selection Sort en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11 for (size_t i = 0; i + 1 < a.size(); ++i) {12 // Find the smallest element in the unsorted suffix13 size_t minIdx = i;14 for (size_t j = i + 1; j < a.size(); ++j) {15 if (a[j] < a[minIdx]) minIdx = j;16 }17 std::swap(a[i], a[minIdx]);18 }19}20
21int main() {22 std::vector<int> data = {29, 10, 14, 37, 13, 5};23 std::cout << "Before: ";24 printVec(data);25 selectionSort(data);26 std::cout << "After: ";27 printVec(data);28 return 0;29}Código de Selection Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void selectionSort(int a[], int n) {9 for (int i = 0; i < n - 1; i++) {10 // Find the smallest element in the unsorted suffix11 int minIdx = i;12 for (int j = i + 1; j < n; j++) {13 if (a[j] < a[minIdx]) minIdx = j;14 }15 int tmp = a[i];16 a[i] = a[minIdx];17 a[minIdx] = tmp;18 }19}20
21int main(void) {22 int data[] = {29, 10, 14, 37, 13, 5};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 selectionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Código de Selection Sort en Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12DECLARE j : INTEGER13DECLARE minIndex : INTEGER14DECLARE temp : INTEGER15
16// Select the smallest remaining value and swap it into place17FOR i ← 1 TO n - 118 minIndex ← i19 FOR j ← i + 1 TO n20 IF nums[j] < nums[minIndex] THEN21 minIndex ← j22 ENDIF23 NEXT j24 IF minIndex <> i THEN25 temp ← nums[i]26 nums[i] ← nums[minIndex]27 nums[minIndex] ← temp28 ENDIF29NEXT i30
31FOR i ← 1 TO n32 OUTPUT nums[i]33NEXT iPreguntas frecuentes sobre Selection Sort
¿Cuál es la complejidad temporal del selection sort?
El selection sort es
O(n²) en todos los casos - mejor, promedio y peor - porque siempre recorre toda la región no ordenada para encontrar cada mínimo. Usa O(1) de espacio extra.¿Es estable el selection sort?
La versión estándar en el lugar no es estable, porque intercambiar un mínimo lejano a su posición puede mover un elemento igual por delante de otro. Existe una variante estable, pero requiere desplazar en lugar de intercambiar.
¿Cuándo es útil el selection sort?
Es útil cuando el costo de escribir en memoria es alto, ya que realiza como máximo
n-1 intercambios - el mínimo posible para un ordenamiento por comparación que mueve elementos.¿Cuál es la diferencia entre selection sort y bubble sort?
Ambos son ordenamientos por comparación
O(n²), pero el selection sort hace como máximo n-1 intercambios mientras que el bubble sort puede hacer hasta O(n²) intercambios. El bubble sort también puede detectar un arreglo ya ordenado y detenerse antes, mientras que el selection sort siempre ejecuta todas las pasadas.¿Debería usar selection sort o insertion sort?
En la mayoría de los casos prefiere el insertion sort: es estable, corre en
O(n) con datos casi ordenados y es más rápido en promedio. Elige el selection sort solo cuando minimizar el número de escrituras sea la prioridad, ya que garantiza como máximo n-1 intercambios.¿Por qué el selection sort siempre corre en O(n²) incluso en un arreglo ordenado?
El selection sort no tiene forma de saber que un elemento ya es el mínimo sin recorrer el resto de la región no ordenada, así que realiza todas las comparaciones en cada pasada sin importar el orden de entrada. Por eso el mejor caso iguala al peor en
O(n²) - a diferencia del insertion o bubble sort, que pueden cortocircuitar.Recursos relacionados
Más visualizaciones
