Análise De Algoritmos De Ordenação

INTRODUÇÃO

Algoritmo de ordenação é um algoritmo que coloca os elementos de uma dada sequência em certa ordem, em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica.

Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.

Este trabalho tem o objetivo de testar alguns desses algoritmos e analisar a eficiência de cada um, e verificar se os tempos obtidos são compatíveis com os estudados teoricamente em sala de aula.

1. TESTES COM OS ALGORITMOS

Os testes foram realizados com os nove algoritmos estudados em sala de aula, todos achados prontos e dispostos na internet, a linguagem utilizada para a codificação foi o Java SE, com o ambiente de programação Eclipse.

1.1 Testes feitos com o vetor em ordem aleatória

O tempo obtido de cada algoritmo pode ser visto na tabela e no gráfico abaixo, com exceção do bucket sort, que acabou apresentando alguns defeitos na hora da execução:

ALGORITMO

TEMPO (EM MILISEGUNDOS)

Insertion Sort

90

Shell Sort

5

Bubble Sort

28

Quick Sort

31

Selection Sort

39

Heap Sort

8

Merge Sort

18

Radix Sort

467

Tabela 01: Tempo dos algoritmos com vetor em ordem aleatória

Como visto, todos os algoritmos tem pouca diferença de tempo se comparado ao radix sort, que consegue ser o mais lento de todos novamente.

1.2 Testes feitos com o vetor em ordem crescente.

O mesmo algoritmo foi usado agora ordenado para verificar os tempos que podem ser vistos da mesma forma abaixo:

ALGORITMO

TEMPO (EM MILISEGUNDOS)

Insertion Sort

0

Shell Sort

7

Bubble Sort

31

Quick Sort

38

Selection Sort

45

Heap Sort

8

Merge Sort

14

Radix Sort

455

Tabela 02: Tempo dos algoritmos com vetor em ordem aleatória

Nesse novo caso, alguns algoritmos