Modelo ABNT

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