En informática , la clasificación por selección es un algoritmo de clasificación por comparación in situ . Tiene una complejidad temporal O ( n 2 ) , lo que lo hace ineficiente en listas grandes y, en general, funciona peor que el tipo de inserción similar . La clasificación por selección destaca por su simplicidad y tiene ventajas de rendimiento sobre algoritmos más complicados en determinadas situaciones, especialmente 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 al principio (izquierda) de la lista y una sublista de los elementos restantes sin clasificar que ocupan el resto de la lista. Inicialmente, la sublista ordenada está vacía y la sublista sin clasificar 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 clasificar, intercambiándolo con el elemento sin clasificar más a la izquierda (poniéndolo en orden) y moviendo los límites de la sublista un elemento hacia la derecha. .
La eficiencia temporal de la clasificación por selección es cuadrática, por lo que existen varias técnicas de clasificación que tienen una mejor complejidad temporal que la clasificación por selección.
A continuación se muestra un ejemplo de este algoritmo de clasificación que ordena cinco elementos:
(No aparece nada 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 listas que hacen que agregar y eliminar sean eficientes, como una lista vinculada . 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:
llegada[] = 64 25 12 22 11// Encuentra el elemento mínimo en arr[0...4]// y lo colocamos al principio11 25 12 22 64// Encuentra el elemento mínimo en arr[1...4]// y lo colocamos al principio de arr[1...4]11 12 25 22 64// Encuentra el elemento mínimo en arr[2...4]// y lo colocamos al principio de arr[2...4]11 12 22 25 64// Encuentra el elemento mínimo en arr[3...4]// y lo colocamos 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 */int yo , j ; int unaLongitud ; // inicializamos 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 clasificar */ /* suponemos que min es el primer elemento */ int jMin = i ; /* prueba con 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 ]) { /* encontró un nuevo mínimo; recuerda su índice */ jMín = j ; } } si ( jMin != i ) { intercambiar ( &a a [ I a a [ jMin ]); }}La clasificación por selección no es difícil de analizar en comparación con otros algoritmos de clasificación, ya que ninguno de los bucles depende de los datos de la matriz. Seleccionar el mínimo requiere escanear elementos (hacer comparaciones) y luego cambiarlos a la primera posición. Encontrar el siguiente elemento más bajo requiere escanear los elementos restantes (realizar comparaciones), etc. 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 clasificación cuadrática (algoritmos de clasificación con un caso promedio simple de Θ( n 2 ) ), la clasificación por selección casi siempre supera a la clasificación por burbujas y a la clasificación por gnomos . La ordenación 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 ordenados. La ventaja de la ordenación por inserción es que solo escanea tantos elementos como necesita para colocar el primer elemento, mientras que la ordenación 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 muchas menos dependiendo del orden en que se encontraba la matriz antes de la ordenación. Puede verse como una ventaja para algunas aplicaciones en tiempo real que la clasificación por selección funcionará de manera idéntica independientemente del orden de la matriz, mientras que el tiempo de ejecución de la clasificació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 número de escrituras ( intercambios versus hasta intercambios, siendo cada intercambio dos escrituras), esto es aproximadamente el doble del mínimo teórico logrado por la ordenación por ciclo , que realiza como máximo n escrituras. Esto puede ser importante si las escrituras son significativamente más caras que las lecturas, como en el caso de la memoria EEPROM o Flash , donde cada escritura reduce la vida útil de la memoria.
La ordenación por selección se puede implementar sin ramas impredecibles en beneficio de los predictores de ramas de la CPU , al encontrar la ubicación del mínimo con código libre de ramas y luego realizar el intercambio incondicionalmente.
Finalmente, la ordenación por selección se ve ampliamente superada en matrices más grandes por algoritmos de divide y vencerás como mergesort . Sin embargo, la clasificación por inserción o la clasificación por selección suelen ser más rápidas para matrices pequeñas (es decir, 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 por selección para sublistas "suficientemente pequeñas".
Heapsort mejora enormemente el algoritmo básico mediante el uso de 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 del bucle interno en la clasificación de selección normal, lo que reducirá el tiempo total de ejecución a .
Una variante bidireccional de clasificación por selección (llamada clasificación de selección doble o, a veces, clasificación de cóctel debido a su similitud con la clasificación de coctelera ) encuentra los valores mínimo y máximo en la lista en cada pasada. Esto requiere tres comparaciones por 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 clasificación de selección normal, pero requiere solo la mitad de pases. un ahorro neto del 25%.
La clasificación por selección se puede implementar como una clasificación estable si, en lugar de intercambiar en el paso 2, el valor mínimo se inserta 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 vinculada, o conduce a la realización de escrituras.
En la variante de clasificación de bingo , los elementos se clasifican mirando repetidamente los elementos restantes para encontrar el mayor valor y moviendo todos los elementos con ese valor a su ubicación final. [1] Al igual que la clasificación por conteo , esta es una variante eficiente si hay muchos valores duplicados: la clasificación por selección pasa por los elementos restantes para cada elemento movido, mientras que la clasificación por bingo realiza 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 se encuentra el siguiente valor como en el siguiente pseudocódigo (las matrices tienen base 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. } comenzar último : = longitud ( A ) - 1 ; { La primera iteración está escrita para que sea muy similar a las siguientes, pero sin cambios. } nextMax := A [ último ] ; para i := last - 1 downto 0 hazlo si A [ i ] > nextMax entonces nextMax := A [ i ] ; mientras que ( último > 0 ) y ( A [ último ] = nextMax ) duran : = último - 1 ; mientras que último > 0 comienza prevMax : = nextMax ; nextMax := A [ último ] ; para i := last - 1 downto 0 hazlo si A [ i ] > nextMax entonces si A [ i ] <> prevMax entonces nextMax := A [ i ] ; de lo contrario, comience el intercambio ( A [ i ] , A [ último ]) ; último := último - 1 ; terminar mientras ( último > 0 ) y ( A [ último ] = nextMax ) duran : = ú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 clasificación de bingo sea más rápida porque ejecuta el bucle interno menos veces que la clasificación de selección.
Este artículo incorpora material de dominio público de Paul E. Black. "Clasificación de bingo". Diccionario de Algoritmos y Estructuras de Datos . NIST .