Algoritmos de Ordenacao

UNIVERSIDADE FEDERAL DE MINAS GERAIS

TRABALHO PRÁTICO 1 – ORDENAÇÃO

Belo Horizonte
2015
INTRODUÇÃO
Dentre os vários tipos de ordenação existentes, as mais comuns são ordenação numérica e ordenação lexicográfica. Existem diversos métodos para chegar a estas ordenações, e estes podem ser comparados em alguns aspectos, como tempo, número de comparações e as movimentações entre as chaves do vetor.
Neste trabalho, serão implementados os algoritmos InsertionSort, SelectionSort, ShellSort, QuickSort, HeapSort e RadixSort e serão feitos testes tanto de ordenação numérica quanto de ordenação lexicográfica.
InsertionSort:
Insere o registro atual na posição correta relativa aos registros à esquerda. Dessa forma, todos os registros maiores que o registro atual são movimentados para frente, de modo a disponibilizar a posição de inserção deste.
Possui a mesma complexidade para comparação e movimentação. No melhor caso (vetor parcialmente ou totalmente ordenado), ela é linear – O(n) – enquanto no pior caso (maior registro no início) e no caso médio (registros maiores próximos ao início) são quadráticas – O(n²). Além disso, é utilizado por ter uma implementação simples e em situações que exigem métodos estáveis de ordenação.
SelectionSort:
Seleciona o menor registro à direita do atual e troca-os de posição. Assim, a posição já percorrida, da esquerda para a direita, sempre possui o registro devido.
Possui ordem de complexidade quadrática – O(n²) – para comparação e linear – O(n) – para movimentação, que são constantes para qualquer vetor de tamanho n (ordem inicial aleatória, crescente ou decrescente). Apesar de ser instável, é muito utilizado para vetores com registros grandes.
ShellSort
É uma extensão do método de inserção. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o vetor a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles.