Saltar al contenido principal

Selection Sort

Selection Sort (ordenamiento por selección) es un algoritmo simple de ordenación que funciona seleccionando el elemento más pequeño (o más grande, según el orden deseado) de la lista y colocándolo en su posición correcta, uno a uno, hasta ordenar toda la lista.

  • No necesita listas adicionales; se hace in-place.
  • Se basa en encontrar repetidamente el mínimo de la parte no ordenada y colocarlo en el siguiente lugar disponible de la parte ordenada.

Algoritmo​

  1. Considerar la lista completa como no ordenada.
  2. Buscar el elemento mínimo dentro de la lista no ordenada.
  3. Intercambiar ese mínimo con el primer elemento de la lista no ordenada.
    • Ahora la primera posición está ordenada.
  4. Repetir el proceso para el resto de la lista (excluyendo las posiciones ya ordenadas):
    • Buscar el mínimo en la sublista restante.
    • Colocarlo en la siguiente posición correcta.
  5. Continuar hasta que todas las posiciones estén ordenadas.

Cómo se organiza la lista internamente​

  • La lista se divide mentalmente en dos partes:
    1. La sublista ordenada al inicio.
    2. La sublista no ordenada al final.
  • En cada iteración, el tamaño de la sublista ordenada aumenta en uno, y la sublista no ordenada disminuye en uno.
  • Después de tantas iteraciones como elementos tenga la lista, toda la lista estará ordenada.

Características clave​

  • Siempre hace n-1 iteraciones si la lista tiene n elementos.
  • Es un algoritmo determinista y estable si se implementa cuidadosamente.
  • Fácil de entender y de implementar, pero no es eficiente para listas grandes, porque siempre busca el mínimo de manera completa en cada paso.

Paso a paso con un ejemplo​

Lista inicial

[8, 3, 5, 1, 4]

Paso 1: Buscar el mínimo en toda la lista [8, 3, 5, 1, 4]

  • Mínimo = 1 → intercambiar con el primer elemento 8
  • Lista ahora: [1, 3, 5, 8, 4]

Paso 2: Buscar el mínimo en la sublista [3, 5, 8, 4]

  • Mínimo = 3 → ya está en la posición correcta
  • Lista ahora: [1, 3, 5, 8, 4]

Paso 3: Buscar el mínimo en [5, 8, 4]

  • Mínimo = 4 → intercambiar con el primer elemento de la sublista 5
  • Lista ahora: [1, 3, 4, 8, 5]

Paso 4: Buscar el mínimo en [8, 5]

  • Mínimo = 5 → intercambiar con 8
  • Lista ahora: [1, 3, 4, 5, 8]

Paso 5: Solo queda [8] → ya está ordenado

Resultado final

[1, 3, 4, 5, 8]