Métodos de Ordenação

Pró Reitoria Acadêmica
Escola de Ciências Exatas e Tecnologia
Curso de Bacharelado em Ciência da Computação

Algoritmos de Ordenação

Adam Evangelista da Silva
Daniel Feitosa Meirelles
Hugo Rogério Pinto de Senna

Manaus – 2013

Sumário

Introdução Os algoritmos de ordenação fazem um importante trabalho nas tarefas práticas e teóricas. A muitos algoritmos de ordenação, de forma que aprender o comportamento destes algoritmos, melhor performance e suas complexidades computacionais se torna indispensável na determinação de algoritmos mais eficientes ou adequados para certos problemas.
Esse trabalho tem como objetivo de mostrar graficamente os melhores resultados para ordenar vetores de tamanho, 100, 1000, 10000 e 1000000 utilizando os métodos de ordenação. As ordenações que serão mostradas são: merge sorte, bubble sort, insertion sort, quick sort e selection sort.
Na lista abaixo estão os itens solicitados pelo trabalho:
1 - Implementar os seguintes metodos de ordenação interna: selection sort, insertion sort, bubble sort, merge sort e quick sort.
2 - Implementar um gerador de vetores de inteiros com valores aleatórios.
3 - Gerar vetores com os tamanhos 100, 1000, 10000 e 1000000.
4 - Ordenar cada um dos vetores gerados com cada um dos métodos de ordenação.
5 - Gerar um gráfico comparativo de cada método através do tamanho do vetor x tempo (em milisegundos).

Desenvolvimento

Segue abaixo como os princípios de como os métodos de ordenação fucionam.

Selection Sort

O SelectionSort é um algoritmo de ordenação que segura uma parte ordenada e outro desordenado da sequência verdadeira, e a cada iteração retira o menor elemento do conjunto não-ordenado e adiciona ao conjunto ordenado. A retirada do menor elemento de uma sequência não ordenada tem complexidade no melhor caso O(n), pois sempre seria necessário percorrer a sequência