Pseudocódigo del ordenamiento por selección

Hay muchas diferentes maneras de ordenar las cartas. Aquí hay una sencilla, llamada ordenamiento por selección, probablemente parecida a cómo ordenaste las cartas arriba:
  1. Encuentra la carta más baja. Intercámbiala con la primera carta.
  2. Encuentra la segunda carta más baja. Intercámbiala con la segunda carta.
  3. Encuentra la tercera carta más baja. Intercámbiala con la tercera carta.
  4. Repite encontrar la siguiente carta más baja e intercambiarla en la posición correcta hasta que el arreglo esté ordenado.
Este algoritmo se llama ordenamiento por selección porque selecciona repetidamente el siguiente elemento más bajo y lo intercambia a su lugar.
Tú mismo puedes ver el algoritmo a continuación. Empieza al usar "Paso" para ver cada paso del algoritmo y luego intenta usar "Reproducir" una vez que lo entiendas para ver todos los pasos hasta el final.
Después de verlo por ti mismo, ¿qué opinas sobre este algoritmo? ¿Qué partes parecen tomar más tiempo? ¿Cómo crees que sería su desempeño en arreglos grandes? Mantén esas preguntas en mente a medida que avanzas e implementas este algoritmo.

Encontrar el índice del elemento mínimo en un subarreglo

Uno de los pasos en el ordenamiento por selección es encontrar la siguiente carta más baja para ponerla en su lugar correcto. Por ejemplo, si el arreglo inicialmente tiene los valores [13, 19, 18, 4, 10], primero tenemos que encontrar el índice del valor más pequeño en el arreglo. Como 4 es el valor más pequeño, el índice del valor más pequeño es 3.
El ordenamiento por selección cambiaría el valor en el índice 3 con el valor en el índice 0, dando [4, 19, 18, 13, 10]. Ahora tenemos que encontrar el índice del segundo valor más pequeño para intercambiarlo al índice 1.
Puede ser difícil escribir el código que encuentre el índice del segundo valor más pequeño en un arreglo. Estoy seguro de que podrías hacerlo, pero hay una mejor manera. Observa que como el valor más pequeño ya fue intercambiado al índice 0, lo que realmente queremos es encontrar el valor más pequeño en la parte del arreglo que inicia en el índice 1.A una sección de un arreglo la llamamos un subarreglo, así que en este caso, queremos el índice del valor más pequeño en el subarreglo que comienza en el índice 1. Para nuestro ejemplo, si el arreglo completo es [4, 19, 18, 13, 10], entonces el valor más pequeño en el subarreglo que empieza en el índice 1 es 10, y tiene índice 4 en el arreglo original. Así que el índice 4 es la ubicación del segundo elemento más pequeño del arreglo completo.
Prueba esa estrategia en el siguiente desafío, y entonces tendrás la mayor parte de lo que necesitas para implementar todo el algoritmo de ordenamiento por selección.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.