Orden de selección en Python

O

Introducción

La clasificación, aunque es una operación básica, es una de las operaciones más importantes que debe realizar una computadora. Es un componente básico de muchos otros algoritmos y procedimientos, como la búsqueda y la fusión. Conocer diferentes algoritmos de clasificación podría ayudarlo a comprender mejor las ideas detrás de los diferentes algoritmos, así como también ayudarlo a idear mejores algoritmos.

El algoritmo de ordenación por selección ordena una matriz encontrando el valor mínimo de la parte no ordenada y luego intercambiándolo con el primer elemento no ordenado. Es un algoritmo in situ, lo que significa que no necesitará asignar listas adicionales. Si bien es lento, todavía se usa como el algoritmo de clasificación principal en sistemas donde la memoria es limitada.

En este artículo, explicaremos cómo funciona el Orden de selección y lo implementaremos en Python. Luego, analizaremos las acciones del algoritmo para conocer su complejidad de tiempo.

Orden de selección

Entonces, ¿cómo funciona la clasificación por selección? La clasificación por selección divide la lista de entrada en dos partes, la parte ordenada que inicialmente está vacía y la parte no ordenada, que inicialmente contiene la lista de todos los elementos. Luego, el algoritmo selecciona el valor mínimo de todo el archivo sin clasificar y lo intercambia con el primer valor sin clasificar, y luego aumenta la parte ordenada en uno.

Una implementación de alto nivel de este tipo se vería así:

def selection_sort(L):
    for i in range(len(L) - 1):
        min_index = argmin(L[i:])
        L[i], L[min_index] = L[min_index], L[i]

En el pseudocódigo anterior, argmin() es una función que devuelve el índice del valor mínimo. El algoritmo usa una variable i para realizar un seguimiento de dónde termina la lista ordenada y dónde comienza la no ordenada. Dado que comenzamos sin elementos ordenados y tomamos el valor mínimo, siempre será el caso de que cada miembro de la parte no ordenada sea mayor que cualquier miembro de la parte ordenada.

La primera línea incrementa el valor de i, la segunda línea busca el índice del valor mínimo y la tercera línea intercambia esos valores. El intercambio funciona porque Python calculó el lado derecho antes de asignar algo al lado izquierdo, por lo que no necesitamos ninguna variable temporal.

Veamos cómo funciona en acción con una lista que contiene los siguientes elementos: [3, 5, 1, 2, 4].

Comenzamos con la lista sin clasificar:

  • 3 5 1 2 4

La sección sin clasificar tiene todos los elementos. Examinamos cada elemento y determinamos que 1 es el elemento más pequeño. Entonces, intercambiamos 1 con 3:

  • 1 5 3 2 4

De los elementos restantes sin clasificar, [5, 3, 2, 4], 2 es el número más bajo. Ahora intercambiamos 2 con 5:

  • 1 2 3 5 4

Este proceso continúa hasta que se ordena la lista:

  • 1 2 3 5 4
  • 1 2 3 4 5
  • 1 2 3 4 5

¡Veamos cómo podemos implementar esto en Python!

Implementación

El truco para implementar este algoritmo es realizar un seguimiento del valor mínimo e intercambiar dos elementos de la lista. Abra un archivo llamado sort.py en su editor favorito e ingrese el siguiente código en él:

def selection_sort(L):
    # i indicates how many items were sorted
    for i in range(len(L)-1):
        # To find the minimum value of the unsorted segment
        # We first assume that the first element is the lowest
        min_index = i
        # We then use j to loop through the remaining elements
        for j in range(i+1, len(L)-1):
            # Update the min_index if the element at j is lower than it
            if L[j] < L[min_index]:
                min_index = j
        # After finding the lowest item of the unsorted regions, swap with the first unsorted item
        L[i], L[min_index] = L[min_index], L[i]

Ahora agreguemos algo de código al archivo para probar el algoritmo:

L = [3, 1, 41, 59, 26, 53, 59]
print(L)
selection_sort(L)

# Let's see the list after we run the Selection Sort
print(L)

Luego puede abrir una terminal y ejecutar para ver los resultados:

$ python sort.py
[3, 1, 41, 59, 26, 53, 59]
[1, 3, 26, 41, 53, 59, 59]

¡La lista estaba ordenada correctamente! Sabemos cómo funciona y podemos implementar el Orden de selección en Python. Entremos en teoría y veamos su desempeño con respecto al tiempo.

Cálculo de la complejidad del tiempo

Entonces, ¿cuánto tiempo se tarda en ordenar por selección para ordenar nuestra lista? Vamos a tomar un enfoque y calcular exactamente cuánto tiempo toma el algoritmo de clasificación de selección, dada una matriz de tamaño n. La primera línea del código es:

def selection_sort(L):

Esta línea no debería tomar tanto ya que solo está configurando la pila de funciones. Decimos que esto es una constante: el tamaño de nuestra entrada no cambia el tiempo que tarda en ejecutarse este código. Digamos que se necesita c1 operaciones para realizar esta línea de código. A continuación, tenemos:

for i in range(len(L)-1):

Este es un poco más complicado. En primer lugar, tenemos dos invocaciones de funciones, len() y range(), que se realizan antes del for comienza el bucle. El costo de len() también es independiente del tamaño en CPython, que es la implementación predeterminada de Python en Windows, Linux y Mac. Esto también es cierto para la inicialización de range(). Llamemos a estos dos juntos c2.

A continuación, tenemos el for, que esta corriendo n - 1 veces. Esto no es una constante, el tamaño de la entrada tiene un impacto en el tiempo que se ejecuta. Así que tenemos que multiplicar el tiempo que tarda un ciclo en completarse por n - 1.

Hay un costo constante para evaluar el in operador, digamos c3. Eso cubre el bucle for externo.

La asignación de variables también se realiza en tiempo constante. Llamaremos a este c4:

min_index = i

Ahora nos encontramos con el bucle for interno. Tiene dos invocaciones de funciones constantes. Digamos que toman c5 operaciones.

Nota ese c5 es diferente de c2, porque range aquí tiene dos argumentos, y aquí se está realizando una operación de suma.

Hasta ahora tenemos c1 + c2 + (n - 1) * (c3 + c4 + c5) operaciones, y luego comienza nuestro ciclo interno, multiplicando todo por …? Bueno, es complicado, pero si miras de cerca, necesitas n - 2 veces en el primer bucle, n - 3 en el segundo y 1 en el último tiempo.

Necesitamos multiplicar todo por la suma de todos los números entre 1 y n - 2. Los matemáticos nos han dicho que la suma sería (n - 2) * (n - 1) / 2. No dude en leer más sobre la suma de números enteros entre 1 y cualquier número positivo x aquí.

El contenido del bucle interno también se completa en un tiempo constante. Asignemos el tiempo que tarda Python en hacer el in, if, la instrucción de asignación y el intercambio de variables toman un tiempo constante arbitrario de c6.

for j in range(i+1, len(L)-1):
    if L[j] < L[min_index]:
        min_index = j
L[i], L[min_index] = L[min_index], L[i]

Todos juntos conseguimos c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6 / 2.

Podemos simplificar esto a: a * n * n + b * n + c, dónde a, b y c que representa los valores de las constantes evaluadas.

Esto se conoce como O (n2). Qué significa eso? En resumen, el rendimiento de nuestro algoritmo se basa en el tamaño al cuadrado de nuestra lista de entrada. Por lo tanto, si duplicamos el tamaño de nuestra lista, ¡el tiempo necesario para ordenarla se multiplicaría por 4! Si dividimos el tamaño de nuestra entrada entre 3, ¡el tiempo se reduciría en 9!

Conclusión

En este artículo, analizamos cómo funciona el ordenamiento por selección y lo implementamos en Python. Luego dividimos el código línea por línea para analizar la complejidad del tiempo del algoritmo.

Aprender algoritmos de clasificación le ayudará a comprender mejor los algoritmos en general. Por lo tanto, en caso de que aún no lo haya hecho, puede consultar nuestra descripción general de los algoritmos de clasificación.

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad