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.
for j in range(len(A) - 1)
podrias ponerfor j in range(len(A) - i - 1)
lo cual reduciria la cantidad de comparaciones.