Comb sort

Comb sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$O(n^2)$
complexidade de espaços pior caso	$O(1)$
Algoritmos

O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente ) é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido em 1980 por Wlodzimierz Dobosiewicz. Mais tarde, foi redescoberto e popularizado por Stephen Lacey e Richard Box em um artigo publicado na revista Byte em Abril de 1991. O Comb sort melhora o Bubble sort, e rivaliza com algoritmos como o Quicksort. A idéia básica é eliminar as tartarugas ou pequenos valores próximos do final da lista, já que em um bubble sort estes retardam a classificação tremendamente. (Coelhos, grandes valores em torno do início da lista, não representam um problema no bubble sort).

O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente.

Na Bubble sort, quando quaisquer dois elementos são comparados, eles sempre têm um gap (distância um do outro) de 1. A idéia básica do Comb sort é que a diferença pode ser muito mais do que um. (O Shell sort também é baseado nesta idéia, mas é uma modificação do insertion sort em vez do bubble sort).

O gap (intervalo) começa como o comprimento da lista a ser ordenada dividida pelo fator de encolhimento (em geral 1,3; veja abaixo), e a lista é ordenada com este valor (arredondado para um inteiro se for necessário) para o gap. Então, a diferença é dividida pelo fator de encolhimento novamente, a lista é ordenada com este novo gap, e o processo se repete até que a diferença seja de 1. Neste ponto, o Comb sort continua usando um espaço de 1 até que a lista esteja totalmente ordenada. A fase final da classificação é, portanto, equivalente a um bubble sort, mas desta vez a maioria dos elementos "tartarugas" já foram tratados, assim o bubble sort será eficiente.

Fator de encolhimento

O fator de encolhimento tem um grande efeito sobre a eficiência do Comb sort. No artigo original, os autores sugeriram 1,3 depois de tentar algumas listas aleatórias e encontrando-se, geralmente as mais eficazes. Um valor muito pequeno retarda o algoritmo porque mais comparações devem ser feitas, ao passo que um valor muito grande não pode tratar um número suficiente de "tartarugas" para ser prático.

O texto descreve uma melhoria no comb sort usando o valor base $1/\left(1-\frac{1}{e^\varphi}\right) \approx 1.247330950103979$ como fator de encolhimento. Ele também contém uma implementação em pseudocódigo com uma tabela de gaps pré-definidos.

Variações

Combsort11

Com um fator de encolhimento de cerca de 1,3, só existem três caminhos possíveis para a lista de gaps terminar: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), ou (11, 8, 6, 4, 3, 2, 1). Experimentos mostram que melhorias significativas de velocidade podem ser feitas se o gap for definido como 11, sempre que, caso contrário, tornar-se 9 ou 10. Esta variação é chamada Combsort11.

Se uma das sequências que começam com 9 ou 10, forem utilizadas, o passo final, com um intervalo de 1 tem menor probabilidade de ordenar os dados sendo necessário então outro passo com gap de 1. Os dados são ordenados quando não ocorrem mais trocas durante uma passagem com gap= 1.

Também é possível usar uma tabela pré-definida, para escolher quais gaps a utilizar em cada passo.

Combsort com diferentes finais

Como muitos outros algoritmos eficientes de ordenação (como o quick sort ou merge sort), o comb sort é mais eficaz em suas passagens anteriores do que durante o passo final, quando ele se assemelha a um bubble sort. O Comb sort pode ser mais eficaz se o método de classificação é mudado uma vez que os gaps cheguem a um número pequeno o suficiente. Por exemplo, uma vez que a diferença chegue a um tamanho de cerca de 10 ou menor, parando o comb sort e fazendo um simples gnome sort ou cocktail sort, ou, melhor ainda, um insertion sort, se aumentará a eficiência global da ordenação.

Outra vantagem deste método é que não há necessidade de manter o controle das operações de troca durante os passos da classificação para saber se a ordenação deve parar ou não.

Implementações

Pseudocódigo

function combsort(array input)

    gap := input.size //initialize gap size

    loop until gap = 1 and swaps = 0
        //update the gap value for a next comb. Below is an example
        gap := int(gap / 1.247330950103979)
        if gap < 1
          //minimum gap is 1
          gap := 1
        end if

        i := 0
        swaps := 0 //see bubblesort for an explanation

        //a single "comb" over the input list
        loop until i + gap >= input.size //see shellsort for similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swaps := 1 // Flag a swap has occurred, so the
                           // list is not guaranteed sorted
            end if
            i := i + 1
        end loop

    end loop
end function

C++

Esta é uma implementação no estilo STL. Ele irá classificar qualquer intervalo entre a primeira e a última. Isso funciona com quaisquer iteradores posteriores, mas é mais eficaz com iteradores de acesso aleatório ou ponteiros.

template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
    static const double shrink_factor = 1.247330950103979;
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type gap = std::distance(first, last);
    bool swaps = true;
 
    while ( (gap > 1) || (swaps == true) ){
        if (gap > 1)
            gap = static_cast<difference_type>(gap/shrink_factor);
 
        swaps = false;
        ForwardIterator itLeft(first);
        ForwardIterator itRight(first); std::advance(itRight, gap);
 
        for ( ; itRight!=last; ++itLeft, ++itRight ){
            if ( (*itRight) < (*itLeft) ){
                std::iter_swap(itLeft, itRight);
                swaps = true;
            }
        }
    }
}

Java

public static <E extends Comparable<? super E>> void sort(E[] input) {
    int gap = input.length;
    boolean swapped = true;
    while (gap > 1 || swapped) {
        if (gap > 1)
            gap = (int) (gap / 1.247330950103979);
 
        int i = 0;
        swapped = false;
        while (i + gap < input.length) {
            if (input[i].compareTo(input[i + gap]) > 0) {
                E t = input[i];
                input[i] = input[i + gap];
                input[i + gap] = t;
                swapped = true;
            }
            i++;
        }
    }
}

C

void combsort(int *arr, int size) {
    float shrink_factor = 1.247330950103979;
    int gap = size, swapped = 1, swap, i;
 
    while ((gap > 1) || swapped) {
        if (gap > 1)
           gap = gap / shrink_factor;
 
        swapped = 0;
        i = 0;
 
        while ((gap + i) < size) {
            if (arr[i] - arr[i + gap] > 0) {
                swap = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = swap;
                swapped = 1;
            }
            ++i;
        }
    }
}

Ruby

def comb_sort(list)
  shrink_factor = 1.247330950103979
  gap = list.size
  swapped = true
 
  until (gap == 1) && !swapped
    gap = gap / shrink_factor
 
    gap = 1 if gap < 1
 
    i = 0
    swapped = false
 
    until (i + gap) >= list.size
      if list[i] > list[i + gap]
        list[i], list[i + gap] = list[i + gap], list[i]
        swapped = true
      end
      i = i + 1
    end
  end
 
  list
end

Ver também

• Bubble sort, um algoritmo geralmente mais lento, é a base do Comb sort.
• Cocktail sort, ou bubble sort bidirecional, é uma variação do bubble sort que também aborda o problema das tartarugas.

Ligações externas

• .NET Implementação do Comb sort e vários outros algoritmos