La ordenación por selección es un algoritmo de ordenación simple. Este algoritmo de clasificación es un algoritmo basado en la comparación en el lugar en el que la lista se divide en dos partes, la parte ordenada en el extremo izquierdo y la parte sin clasificar en el extremo derecho. Inicialmente, la parte ordenada está vacía y la parte sin clasificar es toda la lista.
El elemento más pequeño se selecciona de la matriz sin clasificar y se intercambia con el elemento más a la izquierda, y ese elemento se convierte en parte de la matriz ordenada. Este proceso continúa moviendo el límite de la matriz sin clasificar por un elemento a la derecha.
Este algoritmo no es adecuado para grandes conjuntos de datos, ya que su complejidad media y en el peor de los casos es de Ο(n2), donde n es el número de elementos.
¿Cómo funciona el Ordenamiento por Selección?
Considere el siguiente array representado como ejemplo.
Para la primera posición de la lista ordenada, la lista completa se escanea secuencialmente. La primera posición donde 14 se almacena actualmente, buscamos en toda la lista y encontramos que 10 es el valor más bajo.
Así que reemplazamos 14 por 10. Después de una iteración, 10, que es el valor mínimo de la lista, aparece en la primera posición de la lista ordenada.
Para la segunda posición, donde reside 33, comenzamos a escanear el resto de la lista de manera lineal.
Encontramos que 14 es el segundo valor más bajo de la lista y debería aparecer en el segundo lugar. Intercambiamos estos valores.
Después de dos iteraciones, se colocan dos valores mínimos al principio de manera ordenada.
El mismo proceso se aplica al resto de los elementos de la matriz.
A continuación se muestra una representación pictórica de todo el proceso de clasificación:
Ahora, aprendamos algunos aspectos de programación de la clasificación de selección.
Algoritmo
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
Pseudocódigo
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
Para conocer la implementación de ordenación de selección en lenguaje de programación C, haga clic aquí.