DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
Por: Pyetro Mammoccio • 1/6/2016 • Dissertação • 2.645 Palavras (11 Páginas) • 516 Visualizações
UNIVERSIDADE PAULISTA
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE
ALGORITMOS DE ORDENAÇÃO DE DADOS
SÃO PAULO
2016
UNIVERSIDADE PAULISTA
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE
ALGORITMOS DE ORDENAÇÃO DE DADOS
[pic 1]
SÃO PAULO
2016
Sumário
1- OBJETIVO
2- INTRODUÇÃO
4 -REFERENCIAL TEÓRICO
3.1 – BOLHA (OU BUBBLE SORT)
3.2 – SELEÇÂO
3.3 – QUICK SORT
5 – DESENVOLVIMENTO
6 - RESULTADOS E DISCUSSÃO
7- CONSIDERAÇÔES FINAIS
8 – REFERÊNCIAS BIBLIOGRÁFICAS
9- CÓDIGO FONTE
OBJETIVO
O objetivo deste trabalho é apresentar por meio de gráficos e tabelas o desempenho de três algoritmos de ordenação de vetores em linguagem C, destacando qual demanda mais tempo, qual consome mais recursos da máquina, dentre outros fatores.
INTRODUÇÃO
.Os métodos de ordenação de vetores são muito usados de forma didática, para explicar desde conceitos simples como laços de repetição, até conceitos mais elaborados como a recursão (que é parte vital de um dos métodos abordados nesse trabalho) e também utilizados para pequenas aplicações que viermos a desenvolver ao longo da carreira de desenvolvedor.
Nesta dissertação foram escolhidos três métodos, o método Bolha, o de Seleção e o Quick Sort, que serão melhor descritos neste projeto. Porém de forma introdutória apenas vamos descrever abaixo de forma resumida o funcionamento dos principais métodos de ordenação.
Tanto o método Bolha quanto o de Inserção, quanto o de Seleção, trabalham percorrendo o vetor de posição a posição, o que difere é a forma como é ordenado. No método Bolha a comparação é feita em pares, onde há a troca entre os valores se necessário, deixando sempre os maiores valores à direita e os menores à esquerda. O de Seleção seleciona sempre o menor valor para ficar à esquerda, repetindo essas comparações até o vetor estar ordenado. O de Inserção trabalha de maneira similar ao de seleção, mas inserindo os valores menores à esquerda ao invés de somente selecionar.
O grande diferencial vem no método Quck Sort, onde é escolhida uma posição como Pivô (geralmente a posição central do vetor) a partir dele o vetor é dividido em dois, e então sendo ordenado separadamente, por meio de recursão esse processo vai se repetindo, de forma que as metades desse vetor se fragmentem cada vez mais, até chegar ao caso base que é ter somente um par para ordenar, terminado esse processo o vetor estará então ordenado
Nos próximos capítulos será feita uma análise dentre três métodos de ordenação e serão descritos seus resultados e suas devidas comparações.
4 -REFERENCIAL TEÓRICO
Os três métodos utilizados para análise nesta dissertação são os métodos Bolha, Por Seleção e Quick Sort, os quais serão descritos de forma mais detalhada neste capitulo, os três códigos fonte estão no final desta dissertação.
3.1 – BOLHA (OU BUBBLE SORT)
O método bolha, conhecido em inglês como Bubble Sort é o tipo mais simples de ordenação de vetores, porém também é um dos mais limitados em termos de desempenho, uma vez que esse algoritmo demanda muito tempo de execução quando operamos vetores de tamanho considerável.
O código percorre o valor de posição a posição, verificando se o mesmo está na ordem desejada, caso não esteja é feita a troca entre os valores das posições. Por esse motivo justamente o código não trabalha bem em vetores muito grandes, por ser necessário percorrer posição por posição.
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.
...