Ordenar por selección en Python

Si bien no es el algoritmo de clasificación más rápido, Selection Sort sigue siendo relevante debido a lo eficiente que es el espacio. En este artículo, explicaremos cómo funciona Selection Sort, cómo implementarlo en Python y analizar su complejidad temporal.

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 bloque de construcción en 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 ayudarlo a crear mejores algoritmos.

El algoritmo Selection Sort 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 en el lugar, lo que significa que no necesitará asignar listas adicionales. Si bien es lento, todavía se usa como el principal algoritmo de clasificación en sistemas donde la memoria es limitada.

En este artículo, explicaremos cómo funciona el Ordenamiento por selección y lo implementaremos en Python. Luego desglosaremos las acciones del algoritmo para aprender su complejidad del tiempo.

Clasificación de selección

Entonces, ¿cómo funciona el ordenamiento por selección? La ordenació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 ordenar y lo intercambia con el primer valor sin ordenar, y luego aumenta la parte ordenada en uno.

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

1
2
3
4
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 ocurrirá 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 encuentra 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 nada al lado izquierdo, por lo que no necesitamos variables temporales.

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

Comenzamos con la lista desordenada:

  • 3 5 1 2 4

La sección sin clasificar tiene todos los elementos. Revisamos 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 sin ordenar restantes, [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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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:

1
2
3
4
5
6
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)

A continuación, puede abrir una terminal y ejecutar para ver los resultados:

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

¡La lista se ordenó correctamente! Sabemos cómo funciona y podemos implementar la ordenación por selección en Python. Entremos en algo de teoría y veamos su desempeño con respecto al tiempo.

Cálculo de la complejidad del tiempo

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

1
def selection_sort(L):

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

1
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 de que comience el ciclo for. 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 for, que se ejecuta n - 1 veces. Esto no es una constante, el tamaño de la entrada tiene un impacto en cuánto tiempo 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 operador in, digamos c3. Eso cubre el bucle for externo.

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

1
min_index = i

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

Tenga en cuenta que ‘c5’ es diferente de ‘c2’, porque ‘rango’ aquí tiene dos argumentos, y aquí se está realizando una operación de suma.

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

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. Siéntete libre de leer más sobre la suma de números enteros entre 1 y cualquier número positivo x aquí.

Los contenidos del bucle interno también se completan en tiempo constante. Vamos a asignar el tiempo que tarda Python en hacer la sentencia de asignación in, if y la variable swap ocupa un tiempo constante arbitrario de c6.

1
2
3
4
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 obtenemos c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6 / 2.

Podemos simplificar esto a: a * n * n + b * n + c, donde a, b y c representan los valores de las constantes evaluadas.

Esto se conoce como O(n^2^). ¿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 que se tarda en ordenarla se multiplicaría por 4! Si dividimos el tamaño de nuestra entrada por 3, ¡el tiempo se reduciría por 9!

Conclusión

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

Learning sorting algorithms will help you get a better understanding of algorithms in general. So, in case you haven't already, you can check out our descripción general de los algoritmos de clasificación! /)!