Computação

Trabalho Prático 3 – Ordenação

Fernando Calazans Lopes

[e-mail]

Descrição do Problema

Sejam os algoritmos Quicksort e suas otimizações, Mergesort, Radixsort e Heapsort, deve-se implementá-los,  avaliar o desempenho de cada um deles em diferentes cenários e compará-los considerando o tempo gasto e o número de copias e comparações efetuadas por cada um deles.

Cenário I

Neste cenário foram testadas três entradas distintas ( Estrutura de dados ):

1. Um vetor de inteiros.
2. Uma lista duplamente encadeada de inteiros.
3. Um vetor de registros, sendo um registro composto por um inteiro, dez cadeias de duzentos caractere, um boleano e quatro números reais.

Para cada entrada foi implementado um conjunto de operações específicas, isto é, para cada entrada existe uma função que executa o quicksort, ordena, particiona, inicializaEstrutura e geraAleatório.

Cenário II

Neste cenário foram realizados testes concernentes às otimizações do quicksort. A estrutura de dados usada em todos eles foi um vetor de inteiros de tamanho N. Foram testadas as seguintes otimizações:

• QuickSort cujo pivô é selecionado por mediana de três.
• QuickSort cujo pivô é selecionado por mediana de cinco.
• QuickSort que chama o inserção quando os sub-vetores são menores do que cem.
• QuickSort que chama o inserção quando os sub-vetores são menores do que vinte
• QuickSort  não-recursivo.
• QuickSort não-recursivo que empilha sempre o maior sub-vetor obtido no processo de particionamento.

Foi implementado uma função quicksort para cada caso, uma função particiona para o quicksort mediana de três, uma função particiona para o quicksort mediana de cinco e uma função particiona para os demais quicksort´s, uma função ordena para cada caso exceto nos quicksort´s não recursivos.

Cenário III

Neste cenário foram avaliados os métodos de ordenação mergesort, heapsort e radixexchangesort, e esses foram comparados com a melhor otimização do quicksort avaliada no cenário II.

A estrutura de dados utilizada foi a mesma para todos os métodos: um vetor de inteiros.

Conjunto das principais funções

Cenário I

• FLVazia (TipoLista *Lista)  : Faz lista vazia .
• Insere (TipoItem *x, TipoLista *Lista) : Insere um elemento em uma lista.
• Partição (Indice Esq, Indice Dir, Indice *i, Indice *j, Estrutura1 *Estrutura  ) : Método auxiliar do quicksort. Particiona um vetor em dois sub-vetores.
• Ordena (Indice Esq, Indice Dir, Estrutura1 *Estrutura  ) :  Ordena um vetor de itens. ( Entrada1 ) .
• Ordena2 (Indice Esq, Indice Dir, TipoLista *Estrutura, Apontador E, Apontador D ) :  Ordena uma lista linear. ( Entrada2 )
• Ordena3 (Indice Esq, Indice Dir, Estrutura3 *Estrutura  ) : Ordena um vetor de registros. ( Entrada 3 ).
• GeraAleatorio1 ( Estrutura1 *Estrutura ) : Gera um vetor de números inteiros aleatórios.
• GeraAleatorio2 ( TipoLista *Estrutura, int Quantidade ) :  Gera uma lista de números inteiros aleatórios.
• GeraAleatorio3 ( Estrutura3 *Estrutura  ) :  Gera um vetor de registros com cadeias de caracteres, inteiros, booleanos e números reais aleatórios.
• InicializaEstrutura1 ( Estrutura1 *Estrutura, int Quantidade ) : Inicializa a estrutura da entrada um, alocando memória para os apontadores.
• InicializaEstrutura3 ( Estrutura3 *Estrutura, int Quantidade ) : Inicializa a estrutura da entrada três, alocando memória para os apontadores.

Cenário II

 

Cenário III

...