Ordenación de selección: Algoritmo explicado con Python Ejemplo de código

¿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 ordenación. La ordenación por selección tiene una complejidad temporal de O(n²) donde n es el número total de elementos de la lista. La complejidad temporal 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 ordenar.

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 la siguiente lista como ejemplo.

[ 21,6,9,33,3 ]

La lista anterior debe ordenarse para producir los siguientes resultados

[ 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, las siguientes imágenes ilustran cómo el algoritmo de ordenamiento por selección itera a través de los valores al ordenarlos.

La siguiente imagen muestra la lista desordenada

Paso 1)

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

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)

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.

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

Paso 3)

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.

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

Paso 4)

El valor 33 se compara con el resto de valores.

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

Paso 5)

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

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

Selección Ordenar programa usando Python 3

El siguiente código muestra la implementación de la clasificación por selección utilizando Python 3

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 los siguientes resultados

[3, 6, 9, 21, 33]

Explicación del código

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

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

Define una función llamada selecciónOrdenar
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.
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
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.
Encuentra el valor mínimo en la lista desordenada y lo coloca en su posición adecuada
Actualiza el valor de minValueIndex cuando la condición de intercambio es verdadera
Compara los valores de los números de índice minValueIndex e i para ver si no son iguales
El valor más a la izquierda se almacena en una variable temporal.
El valor más bajo del lado derecho ocupa la primera posición.
El valor que se almacenó en el valor temporal se almacena en la posición que anteriormente ocupaba el valor mínimo.
Devuelve la lista ordenada como resultado de la función.
Crea una lista el que tiene números aleatorios
Imprima la lista ordenada después de llamar a la función de selección Ordenar pasando el como parámetro.

Complejidad temporal de la ordenación por selección

La complejidad de ordenación se utiliza para expresar la cantidad de veces que se ejecuta la ordenación de 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 interno, que compara 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 de la lista.

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

La ordenación por selección tiene tres categorías de complejidad, 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(n²)
Mejores casos – esto ocurre cuando la lista proporcionada ya está ordenada. El algoritmo realiza la cantidad mínima de ejecuciones que se expresa como [Big-Omega] ?(n²)
Caso medio – esto ocurre cuando la lista está en orden aleatorio. La complejidad promedio se expresa como [Big-theta] ?(n²)

La ordenación por selección tiene una complejidad espacial 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

Las siguientes son las ventajas de la ordenación por 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

Las siguientes son las desventajas del ordenamiento por 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 el quicksort, tienen un mejor rendimiento en comparación con el ordenamiento por selección.

Resum

La ordenación por selección es un algoritmo de comparación in situ que se utiliza para ordenar una lista aleatoria y convertirla en una lista ordenada. Tiene una complejidad temporal de O(n)²)
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.
Implementando el pseudocódigo en Python 3 implica el uso de dos bucles for y sentencias if para comprobar si es necesario el intercambio
La complejidad temporal mide la cantidad de pasos necesarios para ordenar la lista.
La complejidad temporal del peor caso ocurre cuando la lista está en orden descendente. Tiene una complejidad temporal de [Big-O] O(n²)
La complejidad temporal del mejor caso ocurre cuando la lista ya está en orden ascendente. Tiene una complejidad temporal de [Big-Omega] ?(n²)
La complejidad temporal del caso promedio ocurre cuando la lista está en orden aleatorio. Tiene una complejidad temporal de [Big-theta] ?(n²)
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 el quicksort, tienen un mejor rendimiento en comparación con la clasificación por selección.

Te podría gustar: