Ordenamiento de listas — Python: Listas

El ordenamiento de listas es una tarea algorítmica básica que a menudo se pregunta en las entrevistas 💼 Sin embargo, en el código real, las listas se ordenan utilizando funciones ya preparadas de la biblioteca estándar. En Python, el ordenamiento se realiza con el método sort():

numbers = [8, 3, 10]
# sort modifica la lista
numbers.sort()
print(numbers)  # => [3, 8, 10]

# Se puede ordenar al revés indicando el parámetro 'reverse'
numbers.sort(reverse=True)
print(numbers)  # => [10, 8, 3]

Normalmente, el entrevistador quiere saber lo siguiente:

• ¿Cuánto sabe el candidato sobre algoritmos en general?
• ¿Es capaz de programar (es decir, puede crear un programa por sí mismo, pensando por sí mismo)?
• ¿Cómo funciona su pensamiento algorítmico?

El conocimiento de los algoritmos realmente afecta cómo pensamos y cuán rápida es nuestra capacidad para comprender. Y aunque es imposible conocer todos los algoritmos, al menos debemos tener una idea de los más cruciales y, idealmente, ser capaces de implementarlos.

Robert Martin en su libro "El Programador Pragmático" habla sobre el enfoque Kata, un concepto tomado de las artes marciales 🥋:

📖 El principio de aprender artes marciales basado en kata es que al repetir un kata miles de veces, un practicante de artes marciales entrena su cuerpo para ciertos tipos de movimientos, llevándolos a un nivel inconsciente. De esta manera, al encontrarse en una situación de combate, el cuerpo actúa "por sí solo" sobre la base de los reflejos, implantados por la repetición múltiple de kata. También se cree que kata tiene un efecto meditativo.

Robert Martin recomienda resolver ocasionalmente pequeños problemas algorítmicos clásicos para mantenerse en forma. Este tema se ha vuelto tan popular que si buscas python github kata, verás muchos repositorios con este tipo de problemas.

Ordenamiento

Hay muchas formas de ordenar una lista. La más popular para la enseñanza es el ordenamiento de burbuja (bubble sort).

El algoritmo recorre repetidamente la lista a ordenar. En cada recorrido, compara pares de elementos y, si están en el orden incorrecto, los intercambia. Se repite N-1 veces o hasta que ya no se necesiten más intercambios, indicando que la lista está ordenada. En cada paso, el siguiente mayor elemento se coloca al final, y el menor se desplaza hacia el principio, "flotando" como una burbuja, de ahí el nombre del algoritmo.

def bubble_sort(coll):
    # La función cambia la lista entrante de coll
    steps_count = len(coll) - 1
    # Declaramos variable swapped, cuyo valor muestra,
    # si se realizó un intercambio de elementos durante el recorrido de la lista
    swapped = True
    # bucle while
    while swapped:
        swapped = False
        # Recorremos la lista y cambiamos los elementos de lugar si el anterior
        # es mayor que el siguiente
        for i in range(steps_count):
            if coll[i] > coll[i + 1]:
                # Usamos asignación múltiple para intercambiar elementos
                coll[i], coll[i + 1] = coll[i + 1], coll[i]
                # Si se hizo un cambio,
                # asignamos a swapped el valor True
                swapped = True
        # Restamos 1 al contador for, porque el elemento más grande ya está
        # al final de la lista
        steps_count -= 1

    return coll

print(bubble_sort([3, 2, 10, -2, 0]))  # => [-2, 0, 2, 3, 10]

Todo el código de esta función se divide en dos niveles:

1. El ciclo interno for recorre la lista de principio a fin, intercambiando elementos en pares si es necesario ajustarlos para mantener el orden.
2. El ciclo externo while, que determina cuándo detenerse. Ten en cuenta que en el peor de los casos, este ciclo se ejecutará len(coll) veces, lo que coincide con el peor caso teórico de este algoritmo, en el que el elemento más grande o más pequeño se encuentre en los extremos opuestos de la lista respecto al orden del array.

💡 El ordenamiento de burbuja es el algoritmo de ordenamiento más simple e intuitivo. Es muy útil poder implementarlo de memoria. Intenta hacerlo en tu propia computadora, sin mirar a la teoría.

Materiales adicionales

1. Ordenamiento con Python 📚 La biblioteca estándar de Python
2. Visualización de algoritmos de ordenamiento