Ordenación de selección: algoritmo explicado con un ejemplo de código Python

¿Qué es la clasificación por selección?

ORDEN DE SELECCIÓN es un algoritmo de clasificación por comparación que se utiliza para ordenar una lista aleatoria de elementos en orden ascendente. La comparación no requiere mucho espacio extra. Sólo requiere un espacio de memoria adicional para la variable temporal.

Esto se conoce como en su lugar clasificación. El tipo de selección tiene un tiempo com.plexidad de O(n2) donde n es el número total de elementos de la lista. el tiempo complexity mide el número de iteraciones necesarias para ordenar la lista. La lista se divide en dos particiones: la primera lista contiene elementos ordenados, mientras que la segunda lista contiene elementos sin clasificar.

De forma predeterminada, la lista ordenada está vacía y la lista sin ordenar contiene todos los elementos. Luego se escanea la lista sin ordenar en busca del valor mínimo, que luego se coloca en la lista ordenada. Este proceso se repite hasta que todos los valores hayan sido comparados y ordenados.

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

El primer elemento de la partición sin clasificar se compara con todos los valores del lado derecho para comprobar si es el valor mínimo. Si no es el valor mínimo, entonces su posición se intercambia con el valor mínimo.

Ejemplo

  • Por ejemplo, si el índice del valor mínimo es 3, entonces el valor del elemento con índice 3 se coloca en el índice 0 mientras que el valor que estaba en el índice 0 se coloca en el índice 3. Si el primer elemento en la partición sin ordenar es el valor mínimo, luego devuelve sus posiciones.
  • El elemento que se ha determinado como valor mínimo se mueve a la partición del lado izquierdo, que es la lista ordenada.
  • El lado particionado ahora tiene un elemento, mientras que el lado no particionado tiene (n – 1) elementos donde n es el número total de elementos en la lista. Este proceso se repite una y otra vez hasta que todos los elementos se hayan comparado y ordenado según sus valores.

Definición del problema

Una lista de elementos que están en orden aleatorio debe ordenarse en orden ascendente. Considere lo siguientewing lista como ejemplo.

[ 21,6,9,33,3 ]

La lista anterior debe ordenarse para producir lo siguientewing dE TRATAMIENTOS

[ 3,6,9,21,33 ]

Solución (algoritmo)

Paso 1) Obtenga el valor de n, que es el tamaño total de la matriz.

Paso 2) Divida la lista en secciones ordenadas y sin clasificar. La sección ordenada está inicialmente vacía mientras que la sección sin clasificar contiene la lista completa

Paso 3) Elija el valor mínimo de la sección no particionada y colóquelo en la sección ordenada.

Paso 4) Repita el proceso (n – 1) veces hasta que se hayan ordenado todos los elementos de la lista.

Representación visual

Dada una lista de cinco elementos, lo siguientewing Las imágenes ilustran cómo el algoritmo de ordenación por selección itera a través de los valores al ordenarlos.

El following la imagen muestra la lista sin ordenar

Representación visual

Paso 1)

Representación visual

El primer valor 21 se compara con el resto de valores para comprobar si es el valor mínimo.

Representación visual

3 es el valor mínimo, por lo que se intercambian las posiciones de 21 y 3. Los valores con fondo verde representan la partición ordenada de la lista.

Paso 2)

Representación visual

El valor 6, que es el primer elemento de la partición sin clasificar, se compara con el resto de los valores para saber si existe un valor inferior.

Representación visual

El valor 6 es el valor mínimo, por lo que mantiene su posición.

Paso 3)

Representación visual

El primer elemento de la lista desordenada con el valor 9 se compara con el resto de valores para comprobar si es el valor mínimo.

Representación visual

El valor 9 es el valor mínimo, por lo que mantiene su posición en la partición ordenada.

Paso 4)

Representación visual

El valor 33 se compara con el resto de valores.

Representación visual

El valor 21 es inferior a 33, por lo que las posiciones se intercambian para producir la nueva lista anterior.

Paso 5)

Representación visual

Solo nos queda un valor en la lista no particionada. Por lo tanto, ya está ordenado.

Representación visual

La lista final es como la que se muestra en la imagen de arriba.

Programa de clasificación de selección usando Python 3

El following El código muestra la implementación de clasificación de selección usando 3 Python

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Ejecutar el código anterior produce lo siguiente.wing dE TRATAMIENTOS

[3, 6, 9, 21, 33]

Explicación del código

La explicación del código es la siguiente.

Programa de clasificación de selección usando Python 3

Aquí está la explicación del código:

  1. Define una función llamada selecciónOrdenar
  2. Obtiene el número total de elementos de la lista. Necesitamos esto para determinar el número de pases que se realizarán al comparar valores.
  3. Bucle exterior. Utiliza el bucle para recorrer los valores de la lista. El número de iteraciones es (n – 1). El valor de n es 5, por lo que (5 – 1) nos da 4. Esto significa que las iteraciones externas se realizarán 4 veces. En cada iteración, el valor de la variable i se asigna a la variable minValueIndex
  4. Bucle interior. Utiliza el bucle para comparar el valor más a la izquierda con los demás valores del lado derecho. Sin embargo, el valor de j no comienza en el índice 0. Comienza en (i + 1). Esto excluye los valores que ya se han ordenado para que nos centremos en los elementos que aún no se han ordenado.
  5. Encuentra el valor mínimo en la lista desordenada y lo coloca en su posición adecuada
  6. Actualiza el valor de minValueIndex cuando la condición de intercambio es verdadera
  7. Compares los valores de los números índice minValueIndex y i para ver si no son iguales
  8. El valor más a la izquierda se almacena en una variable temporal.
  9. El valor más bajo del lado derecho ocupa la primera posición.
  10. El valor que se almacenó en el valor temporal se almacena en la posición que anteriormente ocupaba el valor mínimo.
  11. Devuelve la lista ordenada como resultado de la función.
  12. Crea una lista el que tiene números aleatorios.
  13. Imprima la lista ordenada después de llamar a la función de selección Ordenar pasando el como parámetro.

Tiempo ComplexTipo de selección

el tipo complexity se utiliza para expresar el número de veces de ejecución que se necesitan para ordenar la lista. La implementación tiene dos bucles.

El bucle externo que selecciona los valores uno por uno de la lista se ejecuta n veces, donde n es el número total de valores en la lista.

El bucle interior, que compares el valor del bucle externo con el resto de los valores también se ejecuta n veces, donde n es el número total de elementos en la lista.

Por tanto, el número de ejecuciones es (n * n), que también se puede expresar como O(n2).

El tipo de selección tiene tres categorías de complexidad a saber;

  • Peor de los casos – aquí es donde la lista proporcionada está en orden descendente. El algoritmo realiza el número máximo de ejecuciones que se expresa como [Big-O] O(n2)
  • Mejor caso – esto ocurre cuando la lista proporcionada ya está ordenada. El algoritmo realiza el número mínimo de ejecuciones que se expresa como [Big-Omega] ?(n2)
  • Caso medio – esto ocurre cuando la lista está en orden aleatorio. El promedio complexLa idad se expresa como [Big-theta] ?(n2)

El tipo de selección tiene un espacio com.plexidad de O (1), ya que requiere una variable temporal utilizada para intercambiar valores.

¿Cuándo utilizar la clasificación por selección?

La clasificación por selección se utiliza mejor cuando se desea:

  • Tienes que ordenar una pequeña lista de elementos en orden ascendente.
  • Cuando el costo de intercambiar valores es insignificante
  • También se utiliza cuando necesita asegurarse de que se hayan verificado todos los valores de la lista.

Ventajas de la clasificación por selección

El following son las ventajas del tipo de selección

  • Funciona muy bien en listas pequeñas.
  • Es un algoritmo in situ. No requiere mucho espacio para clasificar. Sólo se requiere un espacio adicional para contener la variable temporal.
  • Funciona bien con artículos que ya han sido clasificados.

Desventajas de la clasificación por selección

El following son las desventajas del tipo de selección.

  • Funciona mal cuando se trabaja en listas enormes.
  • El número de iteraciones realizadas durante la clasificación es n-cuadrado, donde n es el número total de elementos de la lista.
  • Otros algoritmos, como la clasificación rápida, tienen un mejor rendimiento en comparación con la clasificación por selección.

Resumen

  • La clasificación por selección es un algoritmo de comparación in situ que se utiliza para clasificar una lista aleatoria en una lista ordenada. Tiene un tiempo complexidad de O(n2)
  • La lista se divide en dos secciones, ordenada y sin clasificar. El valor mínimo se selecciona de la sección sin clasificar y se coloca en la sección ordenada.
  • Esto se repite hasta que se hayan ordenado todos los elementos.
  • La implementación del pseudocódigo en Python 3 implica el uso de dos bucles for y sentencias if para comprobar si es necesario el intercambio.
  • el tiempo complexity mide el número de pasos necesarios para ordenar la lista.
  • El peor de los casos.plexLa cualidad ocurre cuando la lista está en orden descendente. Tiene un tiempo complexidad de [Big-O] O(n2)
  • El mejor momento complexLa situación ocurre cuando la lista ya está en orden ascendente. Tiene un tiempo complexciudad de [Big-Omega] ?(n2)
  • El tiempo promedio de casos complexLa cualidad ocurre cuando la lista está en orden aleatorio. Tiene un tiempo complexidad de [Big-theta] ?(n2)
  • La clasificación por selección se utiliza mejor cuando tiene una pequeña lista de elementos para clasificar, el costo de intercambiar valores no importa y la verificación de todos los valores es obligatoria.
  • La clasificación por selección no funciona bien en listas enormes
  • Otros algoritmos de clasificación, como la clasificación rápida, tienen un mejor rendimiento en comparación con la clasificación por selección.