Cocktail sort – Wikipédia, a enciclopédia livre

Cocktail sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	${\displaystyle {O}(n^{2})}$
complexidade caso médio	${\displaystyle {O}(n^{2})}$
complexidade melhor caso	${\displaystyle {O}(n)}$
otimo	Não
estabilidade	não-estável
Algoritmos
Esta caixa: ver discutir

Cocktail shaker sort,^[1] também conhecido como bubble sort bidirecional,^[2] cocktail sort, shaker sort (o qual também pode se referir a uma variação do insertion sort), ripple sort, shuffle sort,^[3] 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.

A complexidade do Cocktail shaker sort em notação big-O é ${\displaystyle O(n^{2})}$ para o pior caso e caso médio, mas tende a se aproximar de ${\displaystyle 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 ${\displaystyle O(kn)}$.

${\displaystyle 1+1+1+1+n(1+n(1(1+1+1+1))+1+n(1(1+1+1+1))+1)}$
${\displaystyle 4+n(3+4n+4n)}$
${\displaystyle 4+n(3+8n)}$
${\displaystyle n(n)}$
O(n²)

 void cocktail_sort(int list[10]) {     int length,bottom,top, swapped,i,aux;     length=10;     bottom = 0;     top = length - 1;     swapped = 0;      while(swapped == 0 && bottom < top)//Se não houver troca de posições ou o ponteiro que     {                                   //sobe ultrapassar o que desce, o vetor esta ordenado         swapped = 1;          //Este for é a “ida” para a direita         for(i = bottom; i < top; i = i + 1)         {             if(list[i] > list[i + 1])   //indo pra direita:testa se o próximo é maior             {   //indo pra direita:se o proximo é maior que o atual,                 //troca as posições                 aux=list[i];                 list[i]=list[i+1];                 list[i+1]=aux;                 swapped = 0;             }         }//fecha for         // diminui o  `top` porque o elemento com o maior valor          // já está na direita (atual posição top)         top = top - 1;          //Este for é a “ida” para a esquerda         for(i = top; i > bottom; i = i - 1)         {  if(list[i] < list[i - 1])              {                 aux=list[i];                 list[i]=list[i-1];                 list[i-1]=aux;                 swapped = 0;             }         }         //aumenta o `bottom` porque o menor valor já está         //na posição inicial (bottom)          bottom = bottom + 1;       }//fecha while   }// fim da funçao 

         private static void cocktail(int[] vetor) {     int tamanho, inicio, fim, swap, aux;     tamanho = 10; // para um vetor de 20 elementos     inicio = 0;     fim = tamanho - 1;     swap = 0;     while (swap == 0 && inicio < fim)     {         swap = 1;         for (int i = inicio; i < fim; i = i + 1)         {             if (vetor[i] > vetor[i + 1])             {                 aux = vetor[i];                 vetor[i] = vetor[i + 1];                 vetor[i + 1] = aux;                 swap = 0;             }         }         fim = fim - 1;         for (int i = fim; i > inicio; i = i - 1)         {             if (vetor[i] < vetor[i - 1])             {                 aux = vetor[i];                 vetor[i] = vetor[i - 1];                 vetor[i - 1] = aux;                 swap = 0;             }         }         inicio = inicio + 1;     } } 

    procedure ShakerSort(var A:vetor; n:integer);  var L,R,k,i:integer;  begin     L:=2;     R:=n;     k:=2;     repeat         for i:=L to R do         begin             if A[i-1]>A[i] then             begin                 aux := A[i-1];                 A[i-1] := A[i];                 A[i]:= aux;                          k:=i;             end;         end;         R:=k-1;          for i:=R downto L do         begin             if A[i-1]>A[i] then             begin                 aux := A[i-1];                 A[i-1] := A[i];                 A[i]:= aux;                          k:=i;             end;         end;         L:=k+1;     until L>R; end; 

def sort(array) 	swap = true 	begining = 0 	ending = array.length-1 	while(swap) 		swap = false 		begining.upto ending-1 do |i| 			if(array[i] > array[i+1]) 				aux = array[i] 				array[i] = array[i+1] 				array[i+1] = aux 				swap = true 			end 		end 		ending -= 1 		ending.downto begining+1 do |i| 			if(array[i] < array[i-1]) 				aux = array[i] 				array[i] = array[i-1] 				array[i-1] = aux 				swap = true 			end 		end 		begining += 1 	end 	return array end 

#coding: utf-8  def cocktailSort(lista): 	 	nova_lista = [] 	for j in range(len(lista)): 		for i in range(len(lista)-1): 			if lista[len(lista)-1 - i] < lista[len(lista)-2 - i]: 				lista[len(lista)-1-i],lista[len(lista)-2-i] = lista[len(lista)-2-i],lista[len(lista)-1-i] 			if lista[i] > lista[i+1]: 				lista[i],lista[i+1] = lista[i+1],lista[i] 	return lista 		 print cocktailSort([3, 4, 2, 0, 5, 6, 7,1])