Saltar al contenido

Orden de selección de estructura de datos y algoritmos

septiembre 29, 2021
unsorted array

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 Ο (n2), dónde norte es el número de elementos.

¿Cómo funciona la ordenación por selección?

Considere la siguiente matriz representada como ejemplo.

Matriz sin clasificar

Para la primera posición en la lista ordenada, la lista completa 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.

Orden de selección

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.

Orden de selección

Para la segunda posición, donde reside 33, comenzamos a escanear el resto de la lista de manera lineal.

Orden de selección

Encontramos que 14 es el segundo valor más bajo de la lista y debería aparecer en el segundo lugar. Intercambiamos estos valores.

Orden de selección

Después de dos iteraciones, los dos valores mínimos se colocan al principio de manera ordenada.

Orden de selección

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:

Orden de selecció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í.

close