Cocktail sort

Cocktail sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$O(n^{2})$
Algoritmos

Cocktail sort, também conhecido como Shaker Sort, bubble sort bidirecional (que também pode se referir a uma variante do selection sort), ripple sort, shuttle sort ou happy hour sort, é uma variação do bubble sort que é tanto um algoritmo de ordenação estável quanto uma ordenação por comparação. O algoritmo difere do bubble sort pelo fato de ordenar em ambas as direções em cada passagem através da lista. Este algoritmo de ordenação é apenas ligeiramente mais difícil de implementar do que o bubble sort, e resolve o problema com os chamados coelhos e tartarugas no bubble sort.

Complexidade

$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²)

Implementações

Código em C

 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

Código em C# e Java (sintaxe idêntica)

        private static void cocktail(int[] vetor)
        {
            int tamanho, inicio, fim, swap, aux;
            tamanho = 20; // 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;
            }
        }

Código em Pascal

   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;

Código em Ruby

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

Código em Python

 def cocktailSort(seq):
        swapped = True
        i = 0
        j = len(seq) - 1

        while i < j and swapped:
                for k in range(i, j):
                        if seq[k] > seq[k + 1]:
                                seq[k], seq[k + 1] = seq[k + 1], seq[k]
                                swapped = True
                j = j - 1

                if swapped:
                        swapped = False
                        for k in range(j, i, -1):
                                if seq[k] < seq[k - 1]:
                                        seq[k], seq[k - 1] = seq[k - 1], seq[k]
                                        swapped = True
                i = i + 1

                if not swapped:
                        return seq

print cocktailSort([ 9, 1, 5, 8, 6, 0, 2, 4, 3, 7 ])