Algoritmos de ordenamiento en Python: bubble, merge y quicksort

Los algoritmos de ordenamiento son fundamentales en la programación, ya que permiten organizar datos de manera eficiente. En Python, existen varios métodos para realizar esta tarea, entre los que se destacan el bubble sort, el merge sort y el quicksort. Cada uno de estos algoritmos tiene sus propias características, ventajas y desventajas, lo que los hace adecuados para diferentes tipos de problemas.

En este artículo, exploraremos cómo funcionan estos algoritmos, proporcionando ejemplos prácticos y ejercicios para que puedas poner en práctica lo aprendido. Aprender a ordenar datos es una habilidad esencial para cualquier programador, ya sea que estés trabajando en proyectos simples o en aplicaciones más complejas.

Explicación

El bubble sort es uno de los algoritmos de ordenamiento más sencillos. Funciona comparando elementos adyacentes y cambiándolos de lugar si están en el orden incorrecto. Este proceso se repite hasta que no se requieren más intercambios, lo que indica que la lista está ordenada. Aunque es fácil de implementar, su eficiencia es baja, especialmente para listas grandes, ya que tiene una complejidad de O(n²).

Por otro lado, el merge sort utiliza un enfoque de divide y vencerás. Divide la lista en mitades más pequeñas, las ordena recursivamente y luego combina las listas ordenadas para producir una lista final. Este método es más eficiente que el bubble sort, con una complejidad de O(n log n), lo que lo hace adecuado para conjuntos de datos más grandes.

Finalmente, el quicksort también es un algoritmo de divide y vencerás, pero elige un elemento como pivote y particiona la lista en elementos menores y mayores que el pivote, ordenando así las sublistas de manera recursiva. Su rendimiento promedio es O(n log n), aunque en el peor de los casos puede llegar a O(n²), dependiendo de la elección del pivote.

Ejemplos paso a paso

1. Bubble Sort
   1. Lista inicial: [64, 34, 25, 12, 22, 11, 90]
   2. Comparar 64 y 34, intercambiar: [34, 64, 25, 12, 22, 11, 90]
   3. Comparar 64 y 25, intercambiar: [34, 25, 64, 12, 22, 11, 90]
   4. Continuar comparando e intercambiando hasta que la lista esté ordenada.
2. Merge Sort
   1. Lista inicial: [38, 27, 43, 3, 9, 82, 10]
   2. Dividir en mitades: [38, 27, 43] y [3, 9, 82, 10]
   3. Seguir dividiendo: [38] y [27, 43]; [3, 9] y [82, 10]
   4. Ordenar y combinar las mitades hasta obtener la lista final ordenada.
3. Quicksort
   1. Lista inicial: [10, 80, 30, 90, 40, 50, 70]
   2. Elegir pivote (por ejemplo, 50).
   3. Particionar en menores y mayores: [10, 30, 40] y [80, 90, 70]
   4. Ordenar recursivamente las sublistas.

Ejercicios básicos para practicar

1. Implementa un algoritmo de bubble sort en Python que ordene la lista [5, 1, 4, 2, 8].
2. Aplica el merge sort en la lista [38, 27, 43, 3, 9, 82, 10] y describe el proceso.
3. Escribe un código para realizar quicksort en la lista [3, 6, 8, 10, 1, 2, 1].

1. 
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

print(bubble_sort([5, 1, 4, 2, 8]))

2. 
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        merge_sort(L)
        merge_sort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

3.
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print(quicksort([3, 6, 8, 10, 1, 2, 1]))

Errores frecuentes

• No entender la elección del pivote en quicksort: Elegir un pivote que sea siempre el primer o último elemento puede llevar a un rendimiento deficiente.
• Confundir el orden de los elementos en merge sort: Asegúrate de que estás combinando las listas correctamente, respetando el orden.
• Implementar bubble sort de manera ineficiente: Es fundamental minimizar el número de comparaciones e intercambios.

Preguntas frecuentes

¿Cuál es el algoritmo de ordenamiento más rápido?

El quicksort es generalmente más rápido en la práctica, aunque su rendimiento puede depender de la elección del pivote.

¿Cuándo debería usar merge sort?

El merge sort es útil cuando necesitas estabilidad en el orden y tienes grandes conjuntos de datos.

¿Es el bubble sort útil en la práctica?

El bubble sort es más educativo que práctico, ya que su rendimiento es pobre comparado con otros algoritmos.