APS - Estrutura de dados
Por: frjunior96 • 9/10/2015 • Trabalho acadêmico • 5.642 Palavras (23 Páginas) • 1.224 Visualizações
¬UNIVERSIDADE PAULISTA
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFOMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
PROF. MS. ALDRIANO
Araçatuba – SP
LISTA DE FIGURAS
Figura 1 - Menu Sistema. 21
Figura 2 - Quantidade de elementos do vetor. 22
Figura 3 - Execução do Sistema. 22
Figura 4 - Gráfico comparativo do tempo médio dos algoritmos 23
Figura 5 - Gráfico comparativo do tempo médio Quick Sort 24
Figura 6 - Tabela Comparativa do tempo médio do algoritmo 24
Figura 7 - Gráfico comparativo do tempo médio Quick Sort 25
Figura 8 - Gráfico comparativo do tempo médio Insertion Sort. 26
Figura 9 - Gráfico comparativo do tempo médio Insertion Sort. 26
Figura 10 - Gráfico comparativo do tempo médio Gnome Sort. 27
Figura 11 - Gráfico comparativo do tempo médio Gnome Sort. 28
SUMÁRIO
CAPÍTULO 1 – OBJETIVO DO TRABALHO 4
CAPÍTULO 2 – INTRODUÇÃO 5
CAPÍTULO 3 - REFERENCIAL TEORICO 7
3.1 Quick Sort 8
3.1.1 Insertion Sort 8
3.1.2 Gnome Sort 10
CAPÍTULO 4 – DESENVOLVIMENTO 11
4.1 Inicio do Sistema 11
4.1.1 Metodo de ordenação Gnome Sort 13
4.1.2 Metodo de ordenação Insertion Sort 14
4.1.3 Metodo de ordenação Quick Sort 15
4.1.4 Metodo de ler vetor aleatorio 17
4.1.5 Metodo de ler vetor manualmente 19
4.1.6 Metodo de abrir arquivo de vetor 20
4.1.7 Imagens da tela de execução 21
CAPÍTULO 5 – RESULTADO E DISCUSSÃO 23
5.1 Quick Sort 23
5.1.1 Insertion Sort 25
5.1.2 Gnome Sort 26
CAPÍTULO 6 –CONSIDERAÇÕES FINAIS 29
CAPÍTULO 7 – REFERENCIAS BILIOGRÁFICAS 30
CAPÍTULO 8 – CÓDIGO FONTE 32
Capítulo 1
CAPÍTULO 1 - OBJETIVO DO TRABALHO
O objetivo deste trabalho é analisar a performance de algoritmos de ordenação de dados.
Tais como: Quick Sort, Insertion Sort e Gnome Sort.
O trabalho ira descrever cada um passo a passo e mostrar todas as suas vantagens e desvantagens.
No sistema deve conter o tempo de execução de cada algoritmo, assim vendo qual é mais rápido e eficiente, para podermos descobrir qual performace é melhor.
O sistema deverá conter três tipos de opções de entrada, sendo manualmente, gerado aleatoriamente e acessado por arquivo texto.
Capítulo 2
CAPÍTULO 2 - INTRODUÇÃO
O trabalho será baseado em tipos de ordenação de dados, que vai ser executado em três tipos de métodos diferentes de ordenações, como funciona e as suas principais aplicações. E ao final apresentar um projeto, e que o programa seja executado em uma linguagem C#.
A ordenação de dados é objeto de estudos bastante aprofundados por diversos órgãos, instituições acadêmicas e pesquisadores do mundo inteiro. O resultado desses estudos é comum até a afirmação de que, para cada tipo de aplicação, existe um tipo de algoritmo de ordenação mais apropriado, depois disso, há uma diversidade de conceitos obtidos, cada um muito bem justificado por seus estudiosos e apresentados como mais eficientes, conforme seus conceitos.
Existem vários algoritmos de ordenação de dados, que foram inventados, ou implementados, conforme foram surgindo necessidades de aprimoramentos dos métodos utilizados ao longo das últimas décadas, tendo em vista o aumento da quantidade de dados que passaram a serem registrados de alguma forma.
O objetivo da ordenação é facilitar a recuperação dos dados de uma lista.
Neste trabalho iremos abordar três algoritmos de ordenação (QuickSort, InsertSort, GnomeSort).
O grupo decidiu esses três tipos de algoritmos por ser mais pratico e fácil.
O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada
InsertSort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados.
Algoritmo similar ao Insert Sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma sequência grande de trocas assim como o Bubble Sort
O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.
Existem também outros tipos de algoritmos como, por exemplo, o Bubble sort que é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i
...