Cocktail sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde maio de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Cocktail sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
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[editar | editar código-fonte]





O(n²)

Implementações[editar | editar código-fonte]

Código em C[editar | editar código-fonte]

 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)[editar | editar código-fonte]

        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;
            }
        }

Código em Pascal[editar | editar código-fonte]

   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[editar | editar código-fonte]

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[editar | editar código-fonte]

 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 ])