Selection sort

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos (para el mejor, peor y caso promedio)1.

Este algoritmo mejora ligeramente el desempeño del algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación de intercambio sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones de intercambio que el de la burbuja, por lo que lo mejora en algo. En la siguiente figura los elementos en amarillo están ordenados, el azul es el “elemento actual” (sobre el que se fija la comparación), el rojo el elemento detectado fuera de orden.

Ordenación por selección sobre un vector.

Otra desventaja de este algoritmo respecto a otros, como el de burbuja o de inserción directa, es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Por ejemplo, en el caso de la ordenación de burbuja, se requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no.

Selection sort animation

 

Referencias

  1. Eduardo René Rodríguez Ávila, “El Correcto y Completo Desarrollo de un Algoritmo“, octubre, 2015. DOI: 10.13140/RG.2.1.4759.1128. URL: https://www.researchgate.net/publication/282660374_El_Correcto_y_Completo_Desarrollo_de_un_Algoritmo.
Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s