Cocktail sort

Cocktail sort

classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	${O}(n^{2})$
complexidade caso médio	${O}(n^{2})$
complexidade melhor caso	${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.

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

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 = 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

   
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

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

Referências

↑ Knuth, Donald E. (1973). «Sorting by Exchanging». Art of Computer Programming. 3. Sorting and Searching 1st ed. [S.l.]: Addison-Wesley. pp. 110–111. ISBN 0-201-03803-X
↑ Black, Paul E.; Bockholt, Bob (24 de agosto de 2009). «bidirectional bubble sort». In: Black, Paul E. Dictionary of Algorithms and Data Structures. [S.l.]: National Institute of Standards and Technology. Consultado em 5 fevereiro de 2010
↑ Duhl, Martin (1986). «Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung». HYPERKARL aus der Algorithmischen Darstellung des BUBBLE-SORT-ALGORITHMUS. Projektarbeit (em German). [S.l.]: Technical University of Kaiserslautern !CS1 manut: Língua não reconhecida (link)

v d e Algoritmos de ordenação
Teoria	Algoritmo de ordenação \| Pesquisa binária \| Busca linear \| Ordenação (computação) \| Lista \| Lista duplamente ligada
Exchange sorts	Bubble sort \| Cocktail sort \| Odd-even sort \| Comb sort \| Gnome sort \| Quicksort
Selection sorts	Selection sort \| Heapsort \| Smoothsort \| Cartesian tree sort \| Tournament sort
Insertion sorts	Insertion sort \| Shell sort \| Tree sort \| Library sort \| Patience sorting
Merge sorts	Merge sort \| Strand sort \| Timsort
Outros	Topological sorting \| Sorting network \| Bitonic sorter \| Batcher odd-even mergesort \| Pancake sorting
Ordenações ineficientes/humorísticas	Bogosort (ou "Estou com sort") \| Stooge sort