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

...

4.1.5.5 Herança 21

4.1.5.6 Sobrecarga de métodos 22

4.2.1 Resultados Observados 23

4.2.2 Exemplo de Resultado Final 23

4.2.3 Comparação de Performance 25

5 - RESULTADOS E DISCUSSÕES 26

5.1 Bubble Sort 26

5.2 Insertion Sort 27

5.3 Quick Sort 28

5.4 Selection Sort 29

5.5 Shell Sort 30

5.7 Comparação geral 31

6 CONSIDERAÇÕES FINAIS 32

7 REFERÊNCIAS BIBLIOGRÁFICAS 34

APÊNDICE

A Classe AbstractSort

B Classe FileManager

C Classe Sort

D Classe SortInterface

E Classe SortManager

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

1 - INTRODUÇÃO

Em todo o mundo há uma constante troca de informações. O que podemos definir como informação é uma união de dados organizadamente que vão formar assim uma mensagem, por exemplo, quando conversamos estamos juntando vários dados e organizando de forma que a outra pessoa entenda, sendo assim ao final o que a outra pessoa terá ouvido serão informações que você passou para ela. Essa troca de informações acontece em tudo, desde pequenos insetos, humanos, até mesmo os computadores, seja em forma de códigos, símbolos, números binários.

Ao longo dos anos a forma de acesso a estas informações foram evoluindo hoje podemos encontrar todas muito facilmente pela internet ao invés de ir a uma biblioteca em um monastério e agora com a internet o acesso a elas é muito mais fácil e rápido.

Mas afinal como mantemos estas informações com um acesso tão rápido e prático, onde assim que digitamos um CEP da rua em um site de compras eles são procurados e acessados de forma rápida. Todos os dados precisam ser armazenados em um tipo de estrutura que por meio delas podemos ter um meio de pesquisa mais eficiente e rápida que trazem mais eficiência para o nosso programa. Seria muito mais rápido procurar um código postal se todos as componentes que estão armazenadas em uma estrutura estivessem ordenadas, devido o tempo de processamento de busca. Podemos ver um exemplo de como o tempo influência nos resultados analisando a segunda guerra onde os nazistas tinham a máquina enigma que todos os dias criptografava diferente do dia anterior as mensagens, Alan Turing desenvolveu uma máquina capaz de desvendar a criptografia por trás das mensagens no mesmo dia, se a máquina dele demorasse 72h para decriptografar um enigma que só iria durar 24h seria inútil pois todas as mensagens trocadas seriam velhas.

A performance dos algoritmos é algo fundamental durante o desenvolvimento de programas, elas podem ser fundamentais para programas que necessitam de uma atualização rápida e ágil, por exemplo, num software de previsão de tempo.

Para entendermos melhor como uma estrutura de dados é, deve ser pensado em uma atividade do nosso cotidiano. Quando uma pessoa vai ao banco ela entra em uma fila, que é um tipo de estrutura de dados também que ajuda a organizar mais facilmente a ordem para o atendimento, se todos ficassem fora da fila e bagunçados alguns demorariam muito mais para serem atendidos.

A estrutura de dados tem suas partes mais clássicas que são as bases para outras partes dentro da estrutura de dados. Um vetor é uma estrutura linear e homogênea de dados de um mesmo tipo, uma vez instanciado dentro do programa com um tamanho ele não poderá ser alterado. Podemos ordenar um vetor, utilizando de métodos especiais para este tipo de trabalho e dependendo de cada tipo de dado e a massa de dados inserida pode ser implementado um método mais eficaz.

Os métodos de ordenação podem ser classificados em duas partes: os métodos de ordenação interna e os métodos de ordenação externa. Em um método de ordenação interna qualquer registo pode ser acessado em qualquer momento, além de que o arquivo a ser ordenado cabe todo na memória principal. Já em um método de ordenação externa os registros são acessados em grandes blocos ou sequencialmente, e o arquivo a ser ordenado não cabe na memória principal.

Alguns algoritmos de ordenação conhecidos são: bubble sort, quick sort, shell sort, insert sort, merge sort, selection sort, entre muitos outros. O método bubble sort, ordenação bolha, é um método que faz diversas comparações, verificando o primeiro com o segundo, o segundo com o terceiro e assim em diante, quando há uma comparação e o número da casa seguinte é menor q o anterior eles trocam de “casa” e isso acontece até que todas as comparações tenham sido efetuadas e não tenha nenhum número fora de ordem, até que na última passagem de comparações não tenha nenhuma troca, basicamente os números maiores vão subindo de posição como se fossem bolhas.

O Insert sort é uma estrutura de básica que divide o seu array em duas partes a primeira parte terá as informações que já foram ordenadas e a segunda parte terá o que ainda vai passar pela ordenação. Primeiro ele determina que a primeira posição do array é o lado ordenado, depois ele vai verificando o segundo e vai adicionando ao lado ordenado assim o vetor do lado esquerdo será o ordenado e do direito o desordenado. Ao analisar este processo nota que em um array de poucas casas a ordenação pode ser rápida, no entanto se for um vetor com um grande conjunto de casas o tempo poderá aumentar perdendo um pouco da performance do código.

Em 1959, Shell propôs o método de ordenação chamado hoje por Shell Sort que é uma versão melhorada do método de inserção (Insert sort), devido o meodo ter problemas em relação a troca de itens adjacentes que determinam o ponto de inserção e são efetuados n-1 comparações e movimentações. Mas este método, shell sort pode trocar os itens mais distantes. Ele é ideal para arquivos de tamanho moderado e requer pouca quantidade de código para implementação.

No momento de escolha de qual tipo será a escolha do seu