COMB SORT - Resumo Análise de Circuitos Elétricos 1 PDF

Preview

Summary

Mostra a implementação do Comb sort em C....

Description

ORDENAÇÃO DE DADOS PELO MÉTODO COMB SORT Autor: José Victor Magalhães Gomes. E-mail:[email protected]

1. INTRODUÇÃO O algoritmo Comb Sort ou algoritmo do pente é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. O algoritmo 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 é uma melhoria do Bubble Sort e rivaliza com o Quick Sort. (WIKIPÉDIA, 2019).

2. MÉTODO COMB SORT O algoritmo Comb Sort repetidamente reordena diferentes pares de dados, separados por um intervalo, que é calculado a cada passagem. Esse método é similar ao Bubble Sort, só que mais eficiente. No algoritmo Bubble, quando dois dados são comparados, eles sempre têm um intervalo (distância um do outro) de 1. No caso do Comb Sort, esse intervalo pode ser muito maior que 1. Figura 1: Funcionamento do algoritmo Comb Sort.

1

O algoritmo Comb Sort tem como princípio de funcionamento (como ilustrado na figura 1) uma variável chamada intervalo (gap) que começa com o comprimento do vetor (lista de dados) a ser ordenada dividido pelo fator de encolhimento (valor geralmente 1,3 ou 1,24), e os valores presentes no vetor são ordenados com o valor do intervalo sendo arredondado para um número inteiro. Então, a diferença é dividida pelo fator de encolhimento novamente, com isso os dados são ordenados novamente com um novo valor de intervalo, 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.

2.1 Implementação do Algoritmo Comb Sort. Figura 2: Algoritmo Comb Sort implementado na IDE Falcon C++:

2

Esse algoritmo funciona da seguinte forma dado o tamanho do vetor, uma variável chamada intervalo receberá o valor da divisão entre o tamanho do vetor e o fato de encolhimento. Posteriormente, o algoritmo estará no laço While se o valor do intervalo for maior que 0 e uma variável chamada troca for diferente do valor do tamanho do vetor – 1. Em seguida, dada as condições no laço While forem verdadeiras o algoritmo entrará em um novo laço de repetição o For que iniciará com uma contagem de valor igual a 0 e se encerrará quando o valor da contagem inicial (i) mais o valor do intervalo forem maior ou igual ao valor do tamanho do vetor. O if é responsável por comparar o valor da posição i numero[i] com o valor da posição i + intervalo numero[i + intervalo] se numero[i] for maior numero[i + intervalo] então acontecerá uma troca com ajuda da variável aux. No caso, a aux receberá o valor de numero[i] e numero[i] receberá o valor numero[i + intervalo] e para completa o processo de troca o numero[i + intervalo] recebe o valor da variável aux. Por fim, o intervalo será dividido novamente pelo fator de encolhimento gerando um novo valor que será usado na nova repetição. Quando as condições não forem mais verdadeiras no While o algoritmo se encerra e é gerado na tela o resultado dos valores ordenados. Esse algoritmo foi implementado para que além de ordenar o vetor, também retorne o valor da quantidade de trocas e o valor da quantidade de comparações.

2.2 Implementação do Algoritmo Comb Sort para valores aleatórios. O algoritmo Comb Sort foi implementado para valores aleatório como mostra a imagem abaixo. Para a geração de valores aleatórios foi usado a função Rand junto com um laço de repetição for para preencher o vetor com valores aleatórios, e por fim foi usado um laço de repetição for para chama e imprimir na tela os valores aleatórios obtidos. Esse algoritmo foi implementado para os seguintes valores de tamanho de vetor: 10, 1000 e 10000.

3

Figura 3: Implementação do algoritmo para valores aleatórios.

2.3 Implementação do Algoritmo Comb Sort para valores em ordem crescente. O algoritmo Comb Sort foi implementado para o melhor caso possível que é para valores em ordem crescente como mostra a imagem abaixo. Para a geração de valores em ordem crescente foi usado a função for que varia entre 0 e o valor do tamanho do vetor. Esse algoritmo foi implementado para os seguintes valores de tamanho de vetor: 10, 1000 e 10000.

Figura 4: Implementação do algoritmo para valores em ordem crescente

2.4 Implementação do Algoritmo Comb Sort para valores em ordem decrescente. 4

O algoritmo Comb Sort foi implementado para o pior caso possível que é para valores em ordem decrescente como mostra a imagem abaixo. Para a geração de valores em ordem decrescente foi usado a função for que varia entre tamanho do vetor e o 0 e foi criado uma variável para realizar a contagem invertida. Esse algoritmo foi implementado para os seguintes valores de tamanho de vetor: 10, 1000 e 10000. Figura 5: Implementação do algoritmo para valores em ordem decrescente

3. RESULTADOS E DISCUSSÕES A tabela 1 mostra os valores do desempenho do algoritmo Comb Sort ao lidar com dados na forma aleatória, crescente e decrescente.

Tabela 1: Valores de desempenho para os vetores. Ordem Aleatória

Ordem Crescente

Ordem decrescente

5

Tamanh

Tempo Comp.

Trocas Tempo

(s)

o Vetor 10 1000 10000

0,291 2,334 21,039

Comp.

Trocas Tempo

(s) 36 22022 32964 4

7 3915 56549

0,173 1,437 19,978

Comp.

Trocas

36 22022 32964

9 1512 19132

(s) 36 22022 32964 4

0 0 0

1,246 2,265 24,954

4

Como é evidenciado na tabela 1, o melhor resultado de desempenho como era de ser n espera é o vetor ordenado em ordem crescente que é o melhor caso ( O (¿¿ 2) . Esse melhor ¿ desempenho se da pelo fato que como o vetor está ordenado em ordem crescente não tem – se a necessidade de troca, o que aumenta o desempenho. O pior resultado como era de ser espera é o vetor ordenado em ordem decrescente que é o pior caso ( O (1 )¿ . Esse pior desempenho se da pelo fato que como o vetor está ordenado em ordem crescente tem – se o maior número de trocas possível para esse método, o que ocasiona uma diminuição no desempenho. No caso de uma ordenação aleatória pode – se obter 3 possíveis resultados de desempenho: o melhor caso, o pior caso e o caso intermediário. O caso mais comum para uma ordenação aleatório e o caso intermediário, ou seja, não se obtêm nem o melhor caso e nem o pior caso.

4. CONCLUSÃO O fator de encolhimento tem um grande efeito sobre a eficiência do Comb Sort. No primeiro artigo publicado o valor escolhido pelos cientistas foi de 1,3 depois de tentar milhares de listas, o valor usado nesse trabalho foi o valor de 1,24 que é uma melhoria no desempenho do algoritmo. O Comb Sort é uma melhoria do Bubble Sort, pois o algoritmo Comb Sort eliminar as tartarugas ou pequenos valores próximos ao final da lista, já que no Bubble Sort n estes retardam a classificação tremendamente. O melhor caso ( O(¿¿ 2) possível e quando ¿ os valores estão ordenados e ordem crescente, como descrito anteriormente nesse trabalho não tem – se a necessidade de troca, o pior caso ( O (1 )¿

possível e quando os dados estão

ordenados em ordem decrescente e o algoritmo tem que ordenar de forma decrescente pois

6

vai terá que trocar de posição todos os valores e o caso mediano e quando os valores estão ordenados de forma aleatória pois o algoritmo Comb Sort pode ou não ter que trocar os lugares dos dados no vetor pois o dado pode já estar no lugar certo.

5. REFERENCIAS WIKIPÉDIA. Comb Sort. Disponível em: https://pt.wikipedia.org/wiki/Comb_sort. Acesso em: 24 jun. 2019.

7...