Algoritmos de ordenamiento 1 con Python

 

En esta ocasión vamos a revisar la implementación del algoritmo de ordenamiento del método de la burbuja (Bubble Sort), y el algoritmo del método de la burbuja bidireccional (Cocktail Sort).

Método de la burbuja (Bubble Sort)

El algoritmo de ordenamiento burbuja (bubble sort en inglés) es uno de los algoritmos de ordenamiento más simples. Funciona comparando cada elemento de la lista con el elemento siguiente e intercambiándolos si están en el orden incorrecto. Este proceso se repite para cada par de elementos adyacentes en la lista, desde el principio hasta el final, haciendo que los elementos más grandes se desplacen hacia el final de la lista.

Los pasos de como funciona el algoritmo son los siguientes:

1. Compara el primer elemento con el segundo. Si el primer elemento es mayor que el segundo, intercámbialos.
2. Luego, compara el segundo elemento con el tercero y haz lo mismo: si el segundo es mayor que el tercero, intercámbialos.
3. Continúa este proceso hasta llegar al final de la lista. En este punto, el elemento más grande está en la última posición.
4. Repite los pasos 1-3 para todos los elementos excepto el último, luego para todos los elementos excepto los dos últimos y así sucesivamente.
5. Repite estos pasos hasta que la lista esté completamente ordenada.

El código implementado en Python para el ordenamiento de una lista de números enteros se muestra a continuación, en el que se recibe una lista de números enteros y retorna la lista ordenada:

def bubbleSort(vector: list) -> list:
    size = len(vector)
    for i in range(0, size - 1, 1):
        for j in range(size - 1, i, -1):
            if vector[j - 1] > vector[j]:
                temp = vector[j - 1]
                vector[j - 1] = vector[j]
                vector[j] = temp
    return vector

Método de la burbuja bidireccional (Cocktail Sort)

Cocktail Sort, también conocido como Shaker Sort, es una variante del algoritmo Bubble Sort. Funciona de manera similar a Bubble Sort, pero con una pequeña mejora en la eficiencia. La principal diferencia es que Cocktail Sort ordena la lista en ambos sentidos, hacia arriba y hacia abajo, en lugar de solo hacia arriba como lo hace Bubble Sort. Esto significa que en cada pasada, los elementos más grandes y más pequeños se colocan en sus posiciones correctas, lo que acelera el proceso de ordenamiento.

Aquí está como funciona el algoritmo Cocktail Sort:

1. Arranca desde el principio de la lista. Compara e intercambia los elementos adyacentes si están en el orden incorrecto, de izquierda a derecha, colocando el elemento más grande en su posición correcta.

2. Mueve hacia atrás a través de la lista. Luego, compara e intercambia los elementos de derecha a izquierda, colocando el elemento más pequeño en su posición correcta.

3. Repite los pasos 1 y 2. Continúa alternando entre los pasos 1 y 2 hasta que no haya más intercambios que realizar. Esto significa que la lista está ordenada.

Este proceso de ordenamiento bidireccional permite que los elementos más grandes y más pequeños se muevan hacia sus posiciones correctas de manera más eficiente que el Bubble Sort tradicional, ya que los elementos pueden ser ordenados en ambos sentidos en cada pasada.

El código implementado en Python para el ordenamiento de una lista de números enteros se muestra a continuación, de igual manera que el anterior, este recibe una lista de números enteros y retorna la lista ordenada:

def cocktailSort(vector: list):
    # Determinamos la longitud de la lista
    size = len(vector)
    # Inicializamos las variables que vamos a manejar en el proceso  
    i, j, last = 0, 0, 0
    aux = 0
    left = 0
    right = size
    # Definimos un bucle para repetir el proceso de ordenamiento
    # de derecha a izquierda y de izquierda a derecha
    # hasta que el valor del puntero izquiero sea mayor al puntero derecho
    while (left > right):
        # Realizamos el ordenamiento de derecha a izquierda
        for i in range(right, left, -1):
            if vector[i - 1] > vector[i]:
                aux = vector[i]
                vector[i] = vector[i - 1]
                vector[i - 1] = aux
                last = i
        # Definimos el valor del puntero izquierdo        
        left = last + 1
        # Realizamos el ordenamiento de izquierda a derecha
        for j in range(left, right, 1):
            if vector[j - 1] > vector[j]:
                aux = vector[j]
                vector[j] = vector[j - 1]
                vector[j - 1] = aux
                last = j
        # Definimos el valor del puntero derecho
        right = last - 1
    return vector

Estos dos algoritmos de ordenamiento son bastante básicos, ya que consisten en recorrer la lista entera realizando comparaciones entre los elementos de la misma. Un ejemplo de su resultado puede ser el siguiente:

in: [2, 7, 101, 6, 9, 4, 1, 0, 20, 36, 95, 2, 94, 10, 54, 8]
out: [0, 1, 2, 2, 4, 6, 7, 8, 9, 10, 20, 36, 54, 94, 95, 101]