Selection sort (selección)
El método de ordenamiento por selección (Selection Sort) es un algoritmo sencillo pero eficiente para ordenar listas.
¿Cómo funciona?
- Buscar el mínimo: Encuentra el elemento más pequeño en la lista.
- Intercambiar: Intercambia este elemento con el primer elemento de la lista.
- Repetir: Repite el proceso para el resto de la lista, comenzando desde el segundo elemento, luego el tercero, y así sucesivamente hasta que toda la lista esté ordenada.
Ejemplo en lenguaje C
#include <stdio.h>
// Función para intercambiar dos elementos
void intercambiar(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Función para realizar el ordenamiento por selección
void ordenamientoPorSeleccion(int arr[], int n) {
int i, j, min_idx;
// Mover el límite del subarreglo no ordenado
for (i = 0; i < n-1; i++) {
// Encontrar el elemento mínimo en el subarreglo no ordenado
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Intercambiar el elemento mínimo con el primer elemento
intercambiar(&arr[min_idx], &arr[i]);
}
}
// Función para imprimir un arreglo
void imprimirArreglo(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Arreglo original: \n");
imprimirArreglo(arr, n);
ordenamientoPorSeleccion(arr, n);
printf("Arreglo ordenado: \n");
imprimirArreglo(arr, n);
return 0;
}
Explicación
- Intercambiar: La función intercambiar se utiliza para cambiar dos elementos en el arreglo.
- Ordenamiento: La función ordenamientoPorSeleccion recorre el arreglo, encuentra el elemento mínimo en el subarreglo no ordenado y lo intercambia con el primer elemento del subarreglo.
- Imprimir: La función imprimirArreglo imprime el arreglo.
Pseudocódigo
para i = 0 hasta n-1
mínimo = i
para j = i+1 hasta n
si lista[j] < lista[mínimo]
mínimo = j
intercambiar(lista[i], lista[mínimo])
Ejemplo
Imagina que tienes la lista [29, 10, 14, 37, 13]:
Encuentra el mínimo (10) y cámbialo con el primer elemento (29): [10, 29, 14, 37, 13]
Encuentra el siguiente mínimo (13) y cámbialo con el segundo elemento (29): [10, 13, 14, 37, 29]
Continúa este proceso hasta que la lista esté ordenada: [10, 13, 14, 29, 37]
Ventajas y Desventajas
Ventajas: Es fácil de entender e implementar.
Desventajas: No es muy eficiente para listas grandes, ya que su complejidad es O(n2)
, lo que significa que el tiempo de ejecución aumenta rápidamente con el tamaño de la lista.