Cocktail sort
# Cocktail sort

Cocktail shaker sort, também conhecido como bubble sort bidirecional, cocktail sort, shaker sort (o qual também pode se referir a uma variação do insertion sort), ripple sort, shuffle sort, ou shuttle sort, é uma variante do bubble sort, que é um algoritmo com não-estável e efetua Ordenação por comparação. O algoritmo difere de um bubble sort no qual ordena em ambas as direções a cada iteração sobre a lista. Esse algoritmo de ordenação é levemente mais difícil de implementar que o bubble sort, e e resolve o problema com os chamados coelhos e tartarugas no bubble sort. Ele possui performance levemente superior ao bubble sort, mas não melhora a performance assintótica; assim como o bubble sort, não é muito usado na prática (insertion sort é escolhido para ordenação simples), embora seja usado para fins didáticos.

## Complexidade

A complexidade do Cocktail shaker sort em notação big-O é $O(n^{2})$ para o pior caso e caso médio, mas tende a se aproximar de $O(n)$ se a lista se encontra parcialmente ordenada antes da execução do algoritmo. Por exemplo, se cada elemento se encontra em uma posição cuja distância até sua posição ordenada é k (k ≥ 1), a complexidade do algoritmo se torna $O(kn)$.
$1+1+1+1+n(1+n(1(1+1+1+1))+1+n(1(1+1+1+1))+1)$
$4+n(3+4n+4n)$
$4+n(3+8n)$
$n(n)$
O(n²)