Comb sort
Comb sort | |
---|---|
classe | Algoritmo de ordenação |
estrutura de dados | Array, Listas ligadas |
complexidade pior caso | |
complexidade de espaços pior caso | |
Algoritmos | |
Esta caixa:
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Comb_sort_demo.gif/220px-Comb_sort_demo.gif)
O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente[1]) é 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 ideia 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 ideia básica do Comb sort é que a diferença pode ser muito mais do que um. (O Shell sort também é baseado nesta ideia, 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 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 nove 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
C#
public void Sort() { gap = (int)(values.Count / 1.3); int i = 0; while (gap > 0 && i != values.Count - 1) { i = 0; while ((i + gap) < values.Count) { if (values[i].CompareTo(values[i + gap]) > 0) { Swap(i, (i + gap)); } i++; } gap = (int)(gap / 1.3); } }
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 combo_sort(int matriz[], int tamanho) { int i, j, intervalo, trocado = 1; int aux; intervalo = tamanho; while (intervalo > 1 || trocado == 1) { intervalo = intervalo * 10 / 13; if (intervalo == 9 || intervalo == 10) intervalo = 11; if (intervalo < 1) intervalo = 1; trocado = 0; for (i = 0, j = intervalo; j < tamanho; i++, j++) { if (matriz[i] > matriz[j]) { aux = matriz[i]; matriz[i] = matriz[j]; matriz[j] = aux; trocado = 1; } } } }
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
Referências
- ↑ AZEREDO, Paulo A. (1996). Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de Janeiro: Campus. pp. 32–34. ISBN 85-352-0004-5
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
- Sorting algorithms/Comb sort
Portal das tecnologias de informação