DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

...

3.2 – SELEÇÂO

Esse método consiste ainda na varredura do vetor de ponta a ponta, mas ao invés de percorrer o vetor em pares, trocando-os se necessário, ele seleciona os menores valores para ficar à esquerda, e os maiores à direita, tem o mesmo problema de tempo que o anterior, mesmo que seja mais ágil.

3.3 – QUICK SORT

Esse é sem dúvida o método de ordenação mais rápido, em grande parte por se utilizar da técnica de recursão. Ele consiste na escolha do elemento como pivô, e então dois contadores vão percorrendo o vetor a esquerda e a direita, ordenando cada “metade” do vetor separadamente, esse procedimento é repetido até os dois lados estarem ordenados, utilizando a recursão para dividir essas metades cada vez mais.

5 – DESENVOLVIMENTO

O algoritmo foi elaborado de forma a poder testar os três métodos de ordenação no mesmo programa, para que o mesmo não fique demasiado poluído. O vetor foi criado utilizando-se de uma constante para o tamanho do mesmo, que foi alterada para que pudéssemos ter vários cenários de vetores.

Em todos os casos o vetor foi preenchido de forma aleatória, utilizando da função srand que gera valores aleatórios dentro do laço, para obtermos o tempo que cada algoritmo demandava, foi utilizado uma função chamada GetTickCount que armazena em uma variável inteira, o tempo em milissegundos que foi decorrido até ali, Então foram feitas tabelas que armazenaram os tempos em cada tamanho de vetor, que para que pudesse ser notado uma diferença e também para que de fato pudesse ser gerado um tempo, foram de mil, dez mil, cem mil e um milhão de posições.

---------------------------------------------------------------

6 - RESULTADOS E DISCUSSÃO

Tamanho do vetor

Tempo de processamento no método bolha

tempo de processamento metodo por seleção

tempo de processamento método quick sort

1000

16

16

0

10000

593

483

593

100000

30499

29593

9370

1000000

2409217

3600000

82800

Tabela usada como base para o gráfico a seguir, exibindo a relação tamanho do vetor x método de ordenação x tempo demandado

[pic 2]

Neste gráfico podemos ver a relação entre os tamanhos dos vetores, no eixo das ordenadas e o tempo em milissegundos no eixo das abcissas. Fica evidente no gráfico a diferença do tempo demandado do método quick sort para os demais.

---------------------------------------------------------------

[pic 3]

Gráfico relacionando o método de ordenação para um tamanho fixo de vetor, neste caso o de um milhão de unidades o qual pode ser melhor verificado a discrepância entre os métodos de ordenação, pelo tempo de ordenação

Tamanho do Vetor

Bolha

Quick Sort

Seleção

1000000

2409217

82800

3600000

Tabela simples usada como base para o gráfico acima

---------------------------------------------------------------

7- CONSIDERAÇÔES FINAIS

Esta dissertação teve o fim mais analítico do que propriamente prático, levando-nos a não somente codificar o programa e coloca-lo para funcionar, mas fazer toda uma analise sobre sua execução, levantando e comparando dados sobre o seu funcionamento e podendo então discernir entre o método mais funcional entre os vários disponíveis para ordenação de vetores.

Foi constatado que o método Quick Sort foi o mais eficiente em todos os casos, podendo trabalhar tanto com vetores menores, quanto em vetores de maior expressão, enquanto os outros dois métodos, apesar de terem implementação muito mais simples que o citado acima, demandam muito mais tempo, fazendo cair por terra o conceito de que a quantidade de linhas de código influi diretamente no processamento do sistema que está sendo desenvolvido.

8 – REFERÊNCIAS BIBLIOGRÁFICAS

Algoritmos de Ordenação #5 – Quick Sort. (s.d.). Acesso em 29 de 05 de 2016, disponível em Rafael Toledo: http://www.rafaeltoledo.net/algoritmos-de-ordenacao-5/

Análise da ordenação por inserção. (s.d.). Acesso em 29 de 05 de 2016, disponível em IME-USP: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/insert.html

Farias, R. (s.d.). Estrutura de Dados e Algoritmos. Acesso em 29 de 05 de 2016, disponível em COS-121: http://www.cos.ufrj.br/~rfarias/cos121/aula_05.html

Ordenação QuickSort [C/C++]. (s.d.). Acesso em 29 de 05 de 2016, disponível em VIVA O LINUX: https://www.vivaolinux.com.br/script/Ordenacao-QuickSort

Ordenando vetores usando Linguagem C | Terminal de Informação. (s.d.). Acesso em 29 de 05 de 2016, disponível em Terminal de Informação: http://terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/

---------------------------------------------------------------

9- CÓDIGO FONTE

#include

#include

#include

#include

#define