Método de Selección

El ordenamiento por selección es un algoritmo de ordenamiento basado en la comparación. Ordena una matriz seleccionando repetidamente el elemento más pequeño (o más grande) de la parte no ordenada e intercambiándolo con el primer elemento no ordenado. Este proceso continúa hasta que toda la matriz esté ordenada.

1. Primero encontramos el elemento más pequeño y lo intercambiamos con el primero. De esta manera, el elemento más pequeño queda en su posición correcta.
2. Luego encontramos el más pequeño entre los elementos restantes (o el segundo más pequeño) y lo intercambiamos con el segundo elemento.
3. Seguimos haciendo esto hasta que consigamos mover todos los elementos a la posición correcta.

Análisis de complejidad de la ordenación por selección

Complejidad temporal: O(n 2 ) , ya que hay dos bucles anidados:

• Un bucle para seleccionar un elemento de la matriz uno por uno = O(n)
• Otro bucle para comparar ese elemento con todos los demás elementos de la matriz = O(n)
• Por lo tanto, la complejidad general = O(n) * O(n) = O(n*n) = O(n 2 )

Espacio auxiliar: O(1) ya que la única memoria extra utilizada es para variables temporales.

Ventajas

• Fácil de entender e implementar, lo que lo hace ideal para enseñar conceptos básicos de clasificación.
• Requiere únicamente un espacio de memoria extra constante O(1).
• Requiere menos intercambios (o escrituras en memoria) en comparación con muchos otros algoritmos estándar. Solo la ordenación cíclica lo supera en cuanto a escrituras en memoria. Por lo tanto, puede ser una opción sencilla cuando las escrituras en memoria son costosas.

Desventajas 

• La ordenación por selección tiene una complejidad temporal de O(n^2), lo que la hace más lenta en comparación con algoritmos como Quick Sort o Merge Sort .
• No mantiene el orden relativo de elementos iguales lo que significa que no es estable.

Aplicaciones del Ordenamiento por selección 

• Perfecto para enseñar mecanismos de clasificación fundamentales y diseño de algoritmos.
• Adecuado para listas pequeñas donde la sobrecarga de algoritmos más complejos no está justificada y la escritura en memoria es costosa, ya que requiere menos escrituras de memoria en comparación con otros algoritmos de clasificación estándar.
• El algoritmo de ordenamiento por montículos se basa en el ordenamiento por selección.

Ejemplo en Lenguaje C:

#include <stdio.h>
void selectionSort(int arr[], int n) { 

 int i, j, min_idx;

// Un ciclo para cada elemento del arreglo for 

(i = 0; i < n-1; i++) { 

 // Encontrar el mínimo en el resto del arreglo 

 min_idx = i; 

 for (j = i+1; j < n; j++) 

 if (arr[j] < arr[min_idx]) 

 min_idx = j;

// Intercambiar el mínimo encontrado con el primer elemento 

 int temp = arr[min_idx]; 

 arr[min_idx] = arr[i]; 

 arr[i] = temp; 

 }

}

int main() { 

 int arr[] = {64, 25, 12, 22, 11}; 

 int n = sizeof(arr)/sizeof(arr[0]); 

 int i;

selectionSort(arr, n);
printf("Arreglo ordenado: \n"); 

 for (i=0; i < n; i++) 

 printf("%d ", arr[i]); 

 printf("\n"); 

 return 0;

}

Este código primero busca el elemento más pequeño y lo intercambia con el primer elemento no ordenado del arreglo. Luego, repite el proceso para el resto del arreglo hasta que esté completamente ordenado.  

Video explicativo: