20120516 APS Ordenacao

Universidade Paulista – Campus Limeira
Curso Ciência da Computação

“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORÍTMOS DE ORDENAÇÃO DE DADOS”

Sumário
1.Objetivo 2
2.Introdução 3
3.Referencial Teórico 4
3.1.Bubble Sort 4
3.2.Quick Sort 6
3.3.Merge Sort 10
4.Desenvolvimento 14
4.1.Entrada de dados: geração e obtenção 14
4.2.Ordenação de dados 17
4.3.Interface e Exibição dos dados 17
4.4.Análise de desempenho 18
5.Resultados e Discussão 20
5.1.Algoritmo Bubble Sort 20
1.1.Algoritmo Quick Sort 21
5.2.Algoritmo Merge Sort 22
5.3.Ordenação de dados aleatórios 23
6.Considerações Finais 25
7.Referências 25
8.CÓDIGO FONTE 27

1. Objetivo

Este trabalho tem como objetivo comparar a eficiência de alguns algoritmos de ordenação de dados. Para isso, utilizaremos três tipos de algoritmos: o Bubble Sort, que funciona comparando cada elemento do vetor com o próximo, para verificar se está na ordem desejada; o Quick Sort, onde os elementos são divididos em dois, ordenados de forma independente e depois comparados; e o Merge Sort, que, basicamente, mescla os elementos e os combina. Nos tópicos abaixo, serão listados para cada algoritmo: quais os pontos positivos e negativos, como é feita sua implementação, qual é o seu desempenho em diversas situações, etc.
Será apresentado, também, um sistema para exemplificar as técnicas de ordenação citadas acima. Este sistema será implementado em Java, linguagem abordada neste semestre, e terá como principal função oferecer um meio de comparar o desempenho dos três algoritmos sob pesquisa.
Além disso, serão explicados os métodos de entrada de dados (inserção de dados manualmente e/ou carregamento de arquivo), o processo de ordenação (funcionalidade dos algoritmos apresentados), e a análise de desempenho (estatística das interações de cada algoritmo), com a exibição dos dados em cada um dos tópicos, para melhor entendimento.

2. Introdução

A consulta a dados hoje se tornou parte de nosso