2

Tengo estos dos códigos el siguiente el cual representa el bubble sort es el siguiente:

lista = [5, 4, 3, 2, 1]

def bubble_sort(A):
    #Se comienza con el primer elemento
    for i in range(len(A) - 1):
        for j in range(len(A) - 1):
            if A[j+1] < A[j]:
                A[j], A[j+1] = A[j+1], A[j]
    return(A)


print(bubble_sort(lista))

El segundo el cual pertenece al cocktail sort :

lista = [5, 4, 3, 2, 1]

def cocktail_sort(A):
    #Se comienza desde el ultimo elemento
    for k in range(len(A) - 1, 0, -1):
        swapped = False
        for i in range(k, 0, -1):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swapped = True
        #Se comienza con el primer elemento
        for i in range(k):
            if A[i] > A[i+1]:
                A[i], A[i+1] = A[i+1], A[i]
                swapped = True

        if not swapped:
            return A


print(cocktail_sort(lista))

Se supone que el cocktail sort es mas eficiente que el bubble sort, pero al momento de correlo el bubble sort tarda 54 pasos mientras que el otro tarda 77 pasos, entonces, ¿Se está realizando en verdad un mejoramiento?

1
  • 1
    Solo una pequeña acotacion, en bubble sort en vez de poner for j in range(len(A) - 1) podrias poner for j in range(len(A) - i - 1) lo cual reduciria la cantidad de comparaciones. el 16 jul. 2017 a las 5:03

1 respuesta 1

7

El algoritmo cocktail sort o burbuja bidireccional tiene la misma complejidad de media que el método burbuja simple: O(n2).

Lo que se persigue con el es reducir el número de iteraciones y las comparaciones necesarias en relación a uno de los problemas típicos del método burbuja simple conocido como "liebres y tortugas":

  • La eficiencia del método burbuja está directamente relacionada con la distancia y la dirección en la que un elemento ha de ser movido para que quede ordenado.

  • Los elementos que han de ser movidos en la misma direción sobre la que itera el método sobre el array se mueven relativamente rápidos ya que se benefician de la posibilidad de realizar varios intercambios por iteración.

  • Los elementos que han de ser desplazados en la dirección contraria a la que itera el método se mueven muy lentamente ya que solo pueden ser movidos una posición por cada iteración.

Para paliar lo anterior se idea el método burbuja bidireccional. La idea es simple, por cada iteración recorremos el array de forma alterna en ambas direcciones. Esto implica que cada iteración del método burbuja bidireccional debe ser tomado como dos del método burbuja simple. Su utilidad y mejora solo será visible en los casos en los que existan elementos "tortuga". Tomemos la implementación de los dos métodos que propones con algunas mejoras como la propuesta por @CodigoFasil:

def bubble_sort(A):
    for i in range(len(A) - 1):
        for j in range(len(A) - i - 1):
            if A[j+1] < A[j]:
                A[j], A[j+1] = A[j+1], A[j]


def cocktail_sort(A):
    for k in range(len(A)//2):
        swapped = False
        for i in range(1+k, len(A)-k):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swapped = True                
        if not swapped:
            break

        swapped = False
        for i in range(len(A)-k-1, k, -1):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swapped = True
        if not swapped:
            break

Para tu ejemplo (lista = [5, 4, 3, 2, 1]) usar el método cocktail no parece que sea mucho mejor porque no hay casos tortuga (recorres el array de derecha a izquierda):

  • Método burbuja:
    • Iteraciones: 4
    • Comparaciones: 10
  • Metodo burbuja bidireccional:
    • Iteraciones: 2
    • Comparaciones: 12

Ahora bién , que pasa en el caso en el que existan elementos tortuga como en lista = [11, 1, 2, 3, 4, 6, 7, 8, 9] donde el "11" ha de ser movido a contracorriente:

  • Método burbuja:
    • Iteraciones: 8
    • Comparaciones: 36
  • Metodo burbuja bidireccional:
    • Iteraciones: 1
    • Comparaciones: 16

En este caso totalmente favorable para el método burbuja bidireccional si que vemos diferencias importantes.

Entre ambos extremos hay muchas posibilidades y no siempre va a tener un rendimiento mejor que el burbuja simple. Su mejora real es bastante marginal comparado con otros métodos por lo que se usa con fines académicos casi exclusivamente en realidad.

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.