Ordenação

UNIVERSIDADE FEREDRAL DO RIO GRANDE DO NORTE
INSTITUTO METRÓPOLE DIGITAL
ESTRUTURA DE DADOS BÁSICA

Algoritmos de Ordenação

ALUNOS: Hiago Mayk Gomes de Araújo Rocha
MAT: 2013050649
Ronnypetson Sousa da Silva
MAT: 2013023392
PROFESSOR: João Carlos

Natal –RN
01/08/2013

INTRODUÇÃO
Neste relatório foram implementados quatro algoritmos de ordenação mostrados em sala e foram feitos testes para comparar os tempos de execução de cada um deles em três cenários: entrada aleatória, entrada ordenada crescentemente e entrada ordenada de forma decrescente. Os testes foram realizados com vetores de variados tamanhos e foi utilizado o código para verificação de tempo, disponibilizado no SIGAA pelo professor da disciplina.

Selection Sort
Este é o método de ordenação mais simples. Ele compara cada elemento escolhido com os restantes para poder selecionar o menor (ou maior) e colocar esse menor (ou maior) elemento na primeira posição do vetor e segue procurando o menor, até que o vetor esteja ordenado. Este método é similar a maneira de uma criança ordenar objetos. O algoritmo é de ordem O(n²). O seu melhor caso é quando o vetor está ordenado da forma como se deseja ordenar (crescente ou decrescente). O caso médio é quando o vetor não está ordenado crescentemente e nem de forma decrescente. E o seu pior caso é quando o vetor está ordenado na ordem inversa a que se quer ordenar
(crecente ou decrescente).
Algoritmo:
Segue o algoritmo com a função utilizada para a realização dos testes.

Testes:
Foram realizados 100 testes para cada tamanho do vetor. Os valores estão representados nas tabelas e nos gráficos abaixo.

50
0.00673

100
0.02553

Selection Sort (normal)
300
500
0.26098
0.68577

O gráfico representa o aumento no tempo de execução.

800
1.83223

1000
2.60499

Ordenamos o vetor de forma crescente para obter o tempo para o melhor caso.

50

100

0.00668

0.02502

Selection Sort (Crescente)
300
500