UFU / FACOM /ALGORITMOS E ESTRUTURA DE DADOS / EXERCÍCIO DE IMPMENT.
Ordenação em Tempo Linear
Os algoritmos de ordenação mais eficientes possuem complexidade de tempo Ω(N.LogN), com relação à
comparação de chave, onde N corresponde à quantidade de itens a serem ordenados. Contudo, em
situações especiais, é possível ordenar um vetor em custo O(N), com relação à visita às posições do vetor.
Neste laboratório, você irá experimentar uma dessas condições especiais.
Objetivo
Criar uma função G que ordena um vetor de números em tempo linear.
Experimento
Seja F um arquivo contendo N números. Você deve criar a função linear_sort() que ordena os N números
em memória, em tempo linear. O arquivo ed-sort.xps, no sítio da disciplina, contém informações de
como ordenar em tempo linear.
Restrições
1. O programa deve ser escrito na linguagem C.
2. O programa deve ser codificado conforme o Padrão de Codificação da disciplina (vide sítio no
Piazza).
3. F é um arquivo, do tipo TXT, que contém N > 100.000 números Naturais, separados por um branco.
4. Os números em F variam entre 0..M-1. Há, entre os números, pelo menos um representante dos
valores entre 0..M-1. (Use o sítio random.org para gerar esses números).
5. O programa deve receber em tempo de lançamento e na seguinte ordem os argumentos abaixo:
a. F – nome do arquivo que contém os números a serem ordenados;
b. N – quantidade de números contidos em F.
c. M – o sucessor do maior valor de chave contido em F.
6. O programa deve ser constituído por, pelo menos, três arquivos .c:
a. main.c – contém as seguintes funções
 main(), que deve essencialmente chamar as funções param(),
linear_sort(), apresentar o vetor ordenado e o tempo da ordenação. A
função linear_sort () tem o seguinte protótipo
int * linear_sort (int *v, int N, int M); onde v corresponde a
um vetor preenchido com os números contido em F. A função retorna um vetor
ordenado;
print_msg(), que apresenta mensagens de erro, conforme um código de erro;
b. param.c – contém a função param(), que verifica a correção dos argumentos;
c. sort.c – contém a implementação da função linear_sort(). Essa função consiste,
essencialmente de chamadas a três funções, cada uma dessas funções implementa um
passo da ordenação linear (vide slides).
7. O tempo de execução dos algoritmos deve ser medido por meio de uma função (ex. gettimeofday).
Resultado Esperado
Espera-se que:
1. Você faça uso de compilação separada.
2. Você faça uso de um debugger, em caso de necessidade.
3. Você perceba que em casos especiais é possível ordenar um vetor em tempo linear.