5.8. El ordenamiento por selección¶
El ordenamiento por selección mejora el ordenamiento burbuja haciendo un sólo intercambio por cada pasada a través de la lista. Para hacer esto, un ordenamiento por selección busca el valor mayor a medida que hace una pasada y, después de completar la pasada, lo pone en la ubicación correcta. Al igual que con un ordenamiento burbuja, después de la primera pasada, el ítem mayor está en la ubicación correcta. Después de la segunda pasada, el siguiente mayor está en su ubicación. Este proceso continúa y requiere \(n-1\) pasadas para ordenar los n ítems, ya que el ítem final debe estar en su lugar después de la \((n-1)\)-ésima pasada.
La Figura 3 muestra todo el proceso de ordenamiento. En cada paso, el ítem mayor restante se selecciona y luego se pone en su ubicación correcta. La primera pasada ubica el 93, la segunda pasada ubica el 77, la tercera ubica el 55, y así sucesivamente. La función se muestra en el ActiveCode 1.
Figura 3: ordenamientoPorSeleccion¶
Figura 3: ordenamientoPorSeleccion
Usted habrá notado que el ordenamiento por selección hace el mismo número de comparaciones que el ordenamiento burbuja y por lo tanto también es \(O(n^{2})\). Sin embargo, debido a la reducción en el número de intercambios, el ordenamiento por selección normalmente se ejecuta más rápidamente en pruebas de referencia. De hecho, para nuestra lista, el ordenamiento burbuja hace 20 intercambios, mientras que el ordenamiento por selección hace sólo 8.
Autoevaluación
- [7, 11, 12, 1, 6, 14, 8, 18, 19, 20]
- El ordenamiento por selección es similar al ordenamiento burbuja (el cual parece que usted usó) pero usa menos intercambios
- [7, 11, 12, 14, 19, 1, 6, 18, 8, 20]
- Este resultado parece de un ordenamiento por inserción.
- [11, 7, 12, 14, 1, 6, 8, 18, 19, 20]
- Este resultado se parece a la respuesta correcta pero en lugar de intercambiar los números, estos se han desplazado a la izquierda para dar cabida a los números correctos.
- [11, 7, 12, 14, 8, 1, 6, 18, 19, 20]
- El ordenamiento por selección mejora el ordenamiento burbuja ya que hace menos intercambios.
Q-3: Suponga que usted tiene que ordenar la siguiente lista de números: [11, 7, 12, 14, 19, 1, 6, 18, 8, 20] ¿Cuál de las siguientes listas representa la lista parcialmente ordenada tras tres pasadas completas del ordenamiento por selección?