Orden de selecci贸n en Python

    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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *