En informática , el ordenamiento por selección es un algoritmo de ordenamiento por comparación en el lugar . Tiene una complejidad temporal de O ( n2 ) , lo que lo hace ineficiente en listas grandes y, en general, tiene un peor rendimiento que el ordenamiento por inserción similar . El ordenamiento por selección se destaca por su simplicidad y tiene ventajas de rendimiento sobre algoritmos más complicados en ciertas situaciones, en particular cuando la memoria auxiliar es limitada.
El algoritmo divide la lista de entrada en dos partes: una sublista ordenada de elementos que se construye de izquierda a derecha en la parte delantera (izquierda) de la lista y una sublista de los elementos restantes sin ordenar que ocupan el resto de la lista. Inicialmente, la sublista ordenada está vacía y la sublista sin ordenar es la lista de entrada completa. El algoritmo procede encontrando el elemento más pequeño (o más grande, dependiendo del orden de clasificación) en la sublista sin ordenar, intercambiándolo (cambiándolo) con el elemento sin ordenar más a la izquierda (poniéndolo en orden ordenado) y moviendo los límites de la sublista un elemento a la derecha.
La eficiencia temporal de la ordenación por selección es cuadrática, por lo que hay varias técnicas de ordenación que tienen una complejidad temporal mejor que la ordenación por selección.
A continuación se muestra un ejemplo de este algoritmo de ordenación que ordena cinco elementos:
(Nada parece cambiado en estas dos últimas líneas porque los dos últimos números ya estaban en orden.)
La ordenación por selección también se puede utilizar en estructuras de lista que hacen que la adición y eliminación sean eficientes, como una lista enlazada . En este caso, es más común eliminar el elemento mínimo del resto de la lista y luego insertarlo al final de los valores ordenados hasta el momento. Por ejemplo:
arr[] = 64 25 12 22 11// Encuentra el elemento mínimo en arr[0...4]// y colóquelo al principio11 25 12 22 64// Encuentra el elemento mínimo en arr[1...4]// y colóquelo al comienzo de arr[1...4]11 12 25 22 64// Encuentra el elemento mínimo en arr[2...4]// y colóquelo al comienzo de arr[2...4]11 12 22 25 64// Encuentra el elemento mínimo en arr[3...4]// y colóquelo al principio de arr[3...4]11 12 22 25 64
A continuación se muestra una implementación en C.
/* a[0] a a[aLength-1] es la matriz a ordenar */entero yo , j ; int aLength ; // inicializar a la longitud de a /* avanza la posición a través de todo el array *//* (podría hacer i < aLength-1 porque un solo elemento también es un elemento mínimo) */para ( i = 0 ; i < aLongitud -1 ; i ++ ) { /* encuentra el elemento min en el a[i .. aLength-1] sin ordenar */ /* supongamos que el mínimo es el primer elemento */ int jMin = i ; /* prueba contra los elementos después de i para encontrar el más pequeño */ para ( j = i + 1 ; j < aLongitud ; j ++ ) { /* si este elemento es menor, entonces es el nuevo mínimo */ si ( a [ j ] < a [ jMin ]) { /* se encontró un nuevo mínimo; recuerda su índice */ jMín = j ; } } si ( jMin != i ) { intercambiar ( &a a [ yo ], y un a [ jMin ]); }}El ordenamiento por selección no es difícil de analizar en comparación con otros algoritmos de ordenamiento, ya que ninguno de los bucles depende de los datos de la matriz. Seleccionar el mínimo requiere escanear los elementos (hacer comparaciones) y luego cambiarlo a la primera posición. Encontrar el siguiente elemento más bajo requiere escanear los elementos restantes (hacer comparaciones) y así sucesivamente. Por lo tanto, el número total de comparaciones es
Por progresión aritmética ,
lo cual es complejo en términos de número de comparaciones.
Entre los algoritmos de ordenamiento cuadrático (algoritmos de ordenamiento con un caso promedio simple de Θ( n 2 ) ), el ordenamiento por selección casi siempre supera al ordenamiento por burbuja y al ordenamiento por gnomo . El ordenamiento por inserción es muy similar en el sentido de que después de la k ésima iteración, los primeros elementos de la matriz están en orden ordenado. La ventaja del ordenamiento por inserción es que solo escanea tantos elementos como necesita para colocar el primer elemento, mientras que el ordenamiento por selección debe escanear todos los elementos restantes para encontrar el primer elemento.
Un cálculo simple muestra que, por lo tanto, la ordenación por inserción generalmente realizará aproximadamente la mitad de comparaciones que la ordenación por selección, aunque puede realizar tantas o menos según el orden en que se encontraba la matriz antes de la ordenación. Puede considerarse una ventaja para algunas aplicaciones en tiempo real que la ordenación por selección funcionará de manera idéntica independientemente del orden de la matriz, mientras que el tiempo de ejecución de la ordenación por inserción puede variar considerablemente. Sin embargo, esto suele ser una ventaja para la ordenación por inserción, ya que se ejecuta de manera mucho más eficiente si la matriz ya está ordenada o "casi ordenada".
Si bien la ordenación por selección es preferible a la ordenación por inserción en términos de cantidad de escrituras ( intercambios versus hasta intercambios, donde cada intercambio es dos escrituras), esto es aproximadamente el doble del mínimo teórico alcanzado por la ordenación por ciclo , que realiza como máximo n escrituras. Esto puede ser importante si las escrituras son significativamente más costosas que las lecturas, como con EEPROM o memoria Flash , donde cada escritura reduce la vida útil de la memoria.
La ordenación por selección se puede implementar sin ramas impredecibles para el beneficio de los predictores de ramas de la CPU , al encontrar la ubicación del mínimo con código sin ramas y luego realizar el intercambio de manera incondicional.
Por último, el ordenamiento por selección se ve superado con creces en matrices más grandes por algoritmos de división y conquista, como mergesort . Sin embargo, el ordenamiento por inserción o el ordenamiento por selección suelen ser más rápidos para matrices pequeñas (es decir, de menos de 10 a 20 elementos). Una optimización útil en la práctica para los algoritmos recursivos es cambiar al ordenamiento por inserción o al ordenamiento por selección para sublistas "suficientemente pequeñas".
Heapsort mejora en gran medida el algoritmo básico al utilizar una estructura de datos de montón implícita para acelerar la búsqueda y eliminación del dato más bajo. Si se implementa correctamente, el montón permitirá encontrar el siguiente elemento más bajo en el tiempo en lugar de hacerlo en el bucle interno en la ordenación por selección normal, lo que reduce el tiempo total de ejecución a .
Una variante bidireccional de la ordenación por selección (denominada ordenación por selección doble o, a veces, ordenación por cóctel debido a su similitud con la ordenación por coctelera ) busca tanto los valores mínimos como los máximos de la lista en cada pasada. Esto requiere tres comparaciones por cada dos elementos (se compara un par de elementos, luego el mayor se compara con el máximo y el menor se compara con el mínimo) en lugar de una comparación por elemento de la ordenación por selección normal, pero requiere solo la mitad de las pasadas, lo que supone un ahorro neto del 25 %.
La ordenación por selección se puede implementar como una ordenación estable si, en lugar de intercambiar en el paso 2, se inserta el valor mínimo en la primera posición y los valores intermedios se desplazan hacia arriba. Sin embargo, esta modificación requiere una estructura de datos que admita inserciones o eliminaciones eficientes, como una lista enlazada, o bien lleva a realizar escrituras.
En la variante de ordenación bingo , los elementos se ordenan mirando repetidamente los elementos restantes para encontrar el valor más grande y moviendo todos los elementos con ese valor a su ubicación final. [1] Al igual que la ordenación por conteo , esta es una variante eficiente si hay muchos valores duplicados: la ordenación por selección hace una pasada a través de los elementos restantes por cada elemento movido, mientras que la ordenación Bingo hace una pasada por cada valor . Después de una pasada inicial para encontrar el valor más grande, las pasadas posteriores mueven cada elemento con ese valor a su ubicación final mientras buscan el siguiente valor como en el siguiente pseudocódigo (las matrices se basan en cero y el bucle for incluye los límites superior e inferior, como en Pascal ):
bingo ( matriz A ) { Este procedimiento ordena en orden ascendente moviendo repetidamente el máximo de elementos hasta el final. } begin last := length ( A ) - 1 ; { La primera iteración está escrita para que se parezca mucho a las siguientes, pero sin intercambios. } nextMax := A [ last ] ; for i := last - 1 downto 0 do if A [ i ] > nextMax then nextMax := A [ i ] ; while ( last > 0 ) and ( A [ last ] = nextMax ) do last := last - 1 ; mientras último > 0 hacer comenzar prevMax := nextMax ; nextMax := A [ último ] ; para i := último - 1 hasta 0 hacer si A [ i ] > nextMax entonces si A [ i ] <> prevMax entonces nextMax := A [ i ] ; de lo contrario comenzar intercambiar ( A [ i ] , A [ último ]) ; último := último - 1 ; fin mientras ( último > 0 ) y ( A [ último ] = nextMax ) hacer último := último - 1 ; fin ; fin ; Por lo tanto, si en promedio hay más de dos elementos con el mismo valor, se puede esperar que la ordenación por bingo sea más rápida porque ejecuta el bucle interno menos veces que la ordenación por selección.
Este artículo incorpora material de dominio público de Paul E. Black. "Bingo sort". Diccionario de algoritmos y estructuras de datos . NIST .