Clasificación de selección de estructura de datos y algoritmos
La clasificación por selección es un algoritmo de clasificación simple. Este algoritmo de clasificación es un algoritmo basado en comparación in situ en el que la lista se divide en dos partes, la parte ordenada en el extremo izquierdo y la parte no ordenada en el extremo derecho. Inicialmente, la parte ordenada está vacía y la parte no ordenada es la lista completa.
El elemento más pequeño se selecciona de la matriz no ordenada 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 un elemento hacia la derecha.
Este algoritmo no es adecuado para grandes conjuntos de datos ya que sus complejidades promedio y en el peor de los casos son de Ο (n 2 ), donden es el número de elementos.
¿Cómo funciona el ordenamiento por selección?
Considere la siguiente matriz representada como ejemplo.
Para la primera posición en la lista ordenada, toda la lista se escanea secuencialmente. En la primera posición donde se almacena 14 actualmente, buscamos en toda la lista y encontramos que 10 es el valor más bajo.
Así que reemplazamos 14 con 10. Después de una iteración, 10, que resulta ser el valor mínimo en 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, dos valores mínimos se colocan al principio de manera ordenada.
El mismo proceso se aplica al resto de los elementos de la matriz.
A continuación se muestra una descripción pictórica de todo el proceso de clasificación:
Ahora, aprendamos algunos aspectos de programación del ordenamiento por selección.
Algoritmo
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 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[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
Para conocer la implementación del ordenamiento por selección en el lenguaje de programación C, haga clic aquí .