¿Qué es la clasificación por selección?
SELECTION SORT es un algoritmo de clasificación por comparación que se utiliza para clasificar una lista aleatoria de elementos en orden ascendente. La comparación no requiere mucho espacio adicional. Solo requiere un espacio de memoria adicional para la variable temporal.
Esto se conoce como clasificación en el lugar . El orden de selección tiene una complejidad de tiempo de O (n 2 ) donde n es el número total de elementos en la lista. La complejidad del tiempo mide el número de iteraciones necesarias para ordenar la lista. La lista está dividida en dos particiones: la primera lista contiene elementos ordenados, mientras que la segunda lista contiene elementos no clasificados.
De forma predeterminada, la lista ordenada está vacía y la lista no ordenada contiene todos los elementos. Luego, la lista no clasificada se escanea en busca del valor mínimo, que luego se coloca en la lista ordenada. Este proceso se repite hasta que se hayan comparado y clasificado todos los valores.
En este tutorial de algoritmos, aprenderá:
- ¿Qué es la clasificación por selección?
- ¿Cómo funciona la ordenación por selección?
- Definición del problema
- Solución (algoritmo)
- Representación visual
- Programa de ordenación de selección usando Python 3
- Explicación del código
- Complejidad de tiempo del orden de selección
- ¿Cuándo usar el ordenamiento por selección?
- Ventajas de la clasificación por selección
- Desventajas de la clasificación por selección
¿Cómo funciona la ordenación por selección?
El primer elemento de la partición sin clasificar se compara con todos los valores del lado derecho para verificar 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 clasificar 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 han comparado y clasificado en función de 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 no ordenadas. La sección ordenada está inicialmente vacía, mientras que la sección no ordenada contiene la lista completa
Paso 3) Elija el valor mínimo de la sección sin particiones 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 clasificación de selección itera a través de los valores al clasificarlos.
La siguiente imagen muestra la lista sin clasificar
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 las posiciones de 21 y 3 se intercambian. Los valores con fondo verde representan la partición ordenada de la lista.
Paso 2)
El valor 6, que es el primer elemento en la partición sin clasificar, se compara con el resto de los valores para averiguar si existe un valor más bajo.
El valor 6 es el valor mínimo, por lo que mantiene su posición.
Paso 3)
El primer elemento de la lista sin clasificar con el valor 9 se compara con el resto de los 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 menor que 33, por lo que las posiciones se intercambian para producir la nueva lista anterior.
Paso 5)
Solo nos queda un valor en la lista sin particionar. Por lo tanto, ya está ordenado.
La lista final es como la que se muestra en la imagen de arriba.
Programa de ordenación de selección usando Python 3
El siguiente código muestra la implementación de ordenación por selección usando Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [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 selectionSort
- Obtiene el número total de elementos de la lista. Necesitamos esto para determinar el número de pasadas que se deben realizar al comparar valores.
- Bucle exterior. Utiliza el ciclo para recorrer en iteración los valores de la lista. El número de iteraciones es (n - 1). El valor de n es 5, entonces (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 otros 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 sin clasificar y lo coloca en su posición correcta.
- Actualiza el valor de minValueIndex cuando la condición de intercambio es verdadera
- Compara los valores de los números de índice minValueIndex yi 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 toma la posición 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 Ordenar de selección pasando el como parámetro.
Complejidad de tiempo del orden de selección
La complejidad de la clasificación se utiliza para expresar el número de tiempos de ejecución necesarios para clasificar la lista. La implementación tiene dos bucles.
El ciclo externo que toma 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 ciclo interno, que compara el valor del ciclo 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 (n 2 ).
El tipo de selección tiene tres categorías de complejidad, a saber;
- En el 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 2 )
- 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] Ω (n 2 )
- Caso promedio : esto ocurre cuando la lista está en orden aleatorio. La complejidad promedio se expresa como [Big-theta] ⊝ (n 2 )
El orden de selección tiene una complejidad espacial de O (1) ya que requiere una variable temporal utilizada para intercambiar valores.
¿Cuándo usar el ordenamiento por selección?
La ordenación por selección se utiliza mejor cuando 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 del tipo de selección.
- Funciona muy bien en listas pequeñas.
- Es un algoritmo in situ. No requiere mucho espacio para clasificar. Solo se requiere un espacio adicional para contener la variable temporal.
- Funciona bien en elementos que ya se han ordenado.
Desventajas de la clasificación por selección
Las siguientes 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 en la lista.
- Otros algoritmos, como el ordenamiento rápido, tienen un mejor rendimiento en comparación con el ordenamiento 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 una complejidad de tiempo de O (n 2 )
- La lista se divide en dos secciones, ordenadas y sin clasificar. El valor mínimo se elige 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 declaraciones if para verificar si es necesario el intercambio
- La complejidad del tiempo mide el número de pasos necesarios para ordenar la lista.
- La complejidad temporal del peor de los casos ocurre cuando la lista está en orden descendente. Tiene una complejidad de tiempo de [Big-O] O (n 2 )
- La complejidad del tiempo en el mejor de los casos ocurre cuando la lista ya está en orden ascendente. Tiene una complejidad de tiempo de [Big-Omega] Ω (n 2 )
- La complejidad del tiempo promedio de los casos ocurre cuando la lista está en orden aleatorio. Tiene una complejidad de tiempo de [Big-theta] ⊝ (n 2 )
- 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.
- El ordenamiento por selección no funciona bien en listas grandes
- Otros algoritmos de clasificación, como el ordenamiento rápido, tienen un mejor rendimiento en comparación con el ordenamiento por selección.