Ordenação

Escola Superior de Tecnologia – EST.
Tecnologia em Analise e Desenvolvimento de Sistema.

Relatório – Algoritmos de Ordenação
Selectionsort X Heapso

26/06/2012
Manaus- AM

Relatoria sobre Ordenação.
Algoritmo de ordenação é aquele que classifica seus elementos de acordo com o tipo de dados tratado (numérico, strings), existem vários tipos de algoritmos de ordenação, porém os mais conhecidos são: Insertionsort, Selectionsort, Bublesort, Quicksort, Heapsort e Mergesort.
A razão para implementar um algoritmo de ordenação é a possibilidade de buscar seus dados com mais eficiência.
Foi selecionado dois algoritmos, Selectionsort e Heapsort para realizar experimentos.
Selectionsort: Consiste em um algoritmo que sempre seleciona o menor valor do vetor para a primeira posição (ou maior, dependendo da ordem desejada), posteriormente é selecionado o segundo menor valor para a segunda posição e assim por diante até o fim do vetor.

Ilustração de funcionamento do Selectionsort
Heapsort: Consiste em um algoritmo que também trabalha em forma de seleção normalmente em arvores binarias, ordena através de sucessivas seleções do elemento correto a ser posicionado em um segmento ordenado.
Na ordenação crescente, o primeiro passo é construir o heap máximo, ou seja, o maior elemento fica na raiz, e para a ordenação decrescente deve ser construído o hep mínimo.

Ilustração de funcionamento do Heapsort.

Resultados obtidos nos experimentos
Para testar o desempenho dos algoritmos definidos acima, foi criado um código em C++ para verificar o tempo de execução de cada algoritmo na seguinte situação:
Foram criados três vetores de tamanhos diferentes e estes preenchidos com valores aleatórios. Tais vetores foram submetidos aos algoritmos de ordenação Selectionsort e Heapsort, e certa vez foram preenchidos com números inteiros, outrora com números binários, para avaliar o desempenho no que se desrespeita a tempo de ordenação.
No experimento com algoritmo de