Modelo ABNT
Casos: Modelo ABNT. Pesquise 862.000+ trabalhos acadêmicosPor: aquino22 • 2/4/2014 • 3.650 Palavras (15 Páginas) • 509 Visualizações
FACULDADE ESTÁCIO DE SÁ DE MADUREIRA
RAPHAEL DE AQUINO GONÇALVES
MÉTODOS DE ORDENAÇÃO DE VETORES
RIO DE JANEIRO, RJ
2014
RAPHAEL DE AQUINO GONÇALVES
MÉTODOS DE ORDENÇÃO DE VETORES
Trabalho acadêmico apresentado à disciplina Estrutura de dados, sob a orientação do Prof. Edwillian Maia, no curso Sistemas de Informação como requisito de avaliação.
RIO DE JANEIRO, RJ
2014
SUMÁRIO
1- INTRODUÇÃO 4
2- MÉTODOS DE ORDENAÇÃO 5
3- BUBBLE SORT 5
4- INSERTION SORT 6
5- SELECTION SORT 8
6- SHELL SORT 9
7- QUICK SORT 11
8- MERGE SORT 13
9- TESTES/RESULTADOS 14
10- CONCLUSÃO 17
11- REFERÊNCIA 18
1- INTRODUÇÃO
Em vários momentos do dia a dia, o homem depara-se com a necessidade de consultar dados ordenados. Como exemplo, pode-se citar uma lista telefônica. Imagine como seria consultar o telefone de uma pessoa se os nomes não estivessem classificados em ordem alfabética. Por isso uma das atividades mais utilizada na computação é a ordenação.
As ordens mais utilizadas são as numéricas e as lexicográficas.
Existem diversos algoritmos para ordenação interna. No presente trabalho será apresentada a implementação e os testes de seis destes métodos.
Bubble Sort
Insertion Sort
Selection Sort
Shell Sort
Quick Sort
Heap Sort
Merge Sort
Os testes foram realizados com vetores de números inteiros de tamanho 25 e tipos (ordenados em ordem crescente e decrescente, aleatórios e parcialmente ordenados com apenas 20% dos elementos fora da ordem).
Como medida para a comparação entre os métodos foi colhida durante cada
Teste:
1. Número de comparações entre chaves do vetor;
2. Número de movimentações;
3. Contagem do tempo gasto durante a execução do algoritmo;
2- Métodos de Ordenação
Ordenar corresponde ao processo de rearranjar um conjunto de objetos em ordem ascendente ou descendente. O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado.
Os métodos de ordenação são classificados em dois grandes grupos: ordenação interna e externa.
1. Ordenação Interna: São os métodos que não necessitam de uma memória secundária para o processo, a ordenação é feita na memória principal do computador;
2. Ordenação Externa: Quando o arquivo a ser ordenado não cabe na memória principal e, por isso, tem de ser armazenado em fita ou disco.
A principal diferença entre os dois grupos é que no método de ordenação interna qualquer registro pode ser acessado diretamente, enquanto no método externo é necessário fazer o acesso em blocos.
3- Bubble Sort (Método Bolha)
É o método mais simples em termos de implementação, porém é o menos eficiente.
A ideia principal do algoritmo é percorrer o vetor n - 1 vezes, a cada passagem fazendo flutuar para o início o menor elemento da sequência. Seu uso não é recomendado para vetores com muitos elementos.
Ilustração do funcionamento do algoritmo Bubble Sort.
Implementação
O algoritmo procede da seguinte forma:
1. Zera
...