Terceiro Exercício-Programa

Ordenação de Arquivos de Texto

Entrega: 04 de dezembro

Os objetivos deste exercício-programa são:

• familiarizar-se com o uso de um vetor de ponteiros para guardar strings de vários comprimentos (este é o uso mais freqüente de um vetor de ponteiros);
• aplicar ao caso da ordenação de linhas de texto os vários algoritmos de ordenação estudados em classe;
• comparar experimentalmente os desempenhos desses algoritimos.

Você escreverá um programa que lê um arquivo de texto, ordena as linhas desse arquivo de texto e escreve na saída padrão o arquivo ordenado. Seu programa, chamado ordena, deve ler a entrada padrão, caso ele tenha sido ativado sem nenhum argumento na linha comando, ou o arquivo cujo nome foi passado como argumento na linha de comando. Assim, no Linux, a linha de comando

    ./ordena

faz o programa tomar como arquivo de entrada a entrada padrão, que neste caso é o teclado. Já a linha de comando

    ./ordena arq_entrada

faz o programa tomar como entrada o arquivo arq_entrada. Finalmente, a linha de comando

    ./ordena < arq_entrada

faz o programa tomar como arquivo de entrada a entrada padrão redirecionada, que neste caso é o arquivo arq_entrada.

O programa ordena deve reconhecer as seguintes opções:

• -a<alg>: Usa o algoritmo de ordenação especificado pelo caractere <alg>, que pode ser um dos seguintes caracteres:
  • H para Heapsort;
  • I para ordenação por inserção;
  • M para Mergesort;
  • Q para Quicksort;
  • S para ordenação por seleção.
  Se não houver -a<alg>, a ordenação é feita com o Quicksort.
• -f: Não faz distinção entre letras minúsculas e maiúsculas, ordenando as linhas como se todas as letras minúsculas fossem maiúsculas ("fold lower case to upper case characters").
• -n: Considera que cada linha começa com um campo numérico e faz a ordenação pelo valor desse campo (que deve ser um número inteiro)
• -r: Gera um arquivo com as linhas em ordem decrescente (ordenação reversa). Se não houver -r, o arquivo de saída é gerado com as linhas em ordem crescente.
• -t: Mede o tempo (em segundos) gasto na função de ordenação e apresenta essa informação na saída de erro padrão.

Exemplo: a linha de comando

    ./ordena -r -f -aM arq_entrada

faz ordenação reversa (decrescente) do arquivo arq_entrada, considerando as letras minúsculas como maiúsculas e usando o algoritmo Mergesort.

Requisitos

• Seu programa deve representar a seqüência de linhas de texto como um vetor de ponteiros (cada ponteiro aponta para uma string contendo uma linha), conforme vimos em classe. Os algoritmnos de ordenação devem manipular esse vetor de ponteiros.
• Todo o arquivo de entrada deve ser lido para um "vetorzão" de chars com espaço suficiente para o arquivo inteiro. Nesse vetorzão, cada linha do arquivo será terminada pelo caractere nulo ('\0'). Em outras palavras, os terminadores de linha '\n' devem ser trocados por '\0' quando o arquivo de entrada for lido. Se não houver um '\n' ao final da última linha do arquivo, mesmo assim essa linha deverá aparecer no vetorzão terminada por um '\0'. É importante o '\0' ao final de cada linha para que todas as linhas sejam strings e, portanto, possam ser passadas como parâmetro para funções que esperam strings. Em particular, isso permite que função strcmp seja usada para comparar linhas.
• O vetorzão de chars deve ser alocado dinamicamente (via malloc). Quando o nome do arquivo de entrada for especificado na linha de comando (ou seja, quando a entrada para o programa ordena não for a entrada padrão), esse vetor deve ser alocado com tamanho igual ao tamanho do arquivo de entrada mais um. (O "mais um" prevê a possibilidade de não haver um '\n' ao final da última linha do arquivo de entrada.) Quando a entrada para o programa ordena for a entrada padrão, o vetorzão deve ser alocado com espaço para 40000000 caracteres.
• O vetor de ponteiros que representa a seqüência das linhas de texto também deve ser alocado dinâmicamente. Ele deve ter comprimento igual ao número de linhas do arquivo de entrada.
• Seu programa deve ter uma função de ordenação para cada um dos algoritmos de ordenação implementados. Com o objetivo de evitar a reimplementação de cada algoritmo de ordenação para os diferentes critérios de ordenação (ordenação lexicográfica normal, ordenação considerendo minúsculas como maiúsculas, ordenação pelo campo numérico inicial), faça suas funções de ordenação receberem, como um parâmetro adicional, um ponteiro para a função de comparação que deve ser utilizada. Esse parâmetro deve ser declarado como

        int (*cmp)(char [], char []) /* ponteiro para função que recebe dois vetores de chars e devolve int */
  

  conforme vimos em classe.

Experimentos

Efetue uma série de experimentos com seu programa, com o objetivo de comparar os tempos de execução dos diferentes algoritmos de ordenação para arquivos de vários tamanhos e características (arquivos já em ordem crescente ou decrescente, arquivos parcialmente ordenados, arquivos não ordenados). Verifique se as complexidades teóricas dos algoritmos são confirmadas pelos seus experimentos. Entregue, juntamente com seu programa, um relatório com os resultados dos experimentos.

Avisos

Este trabalho deve ser entregue até 04/12, através do sistema Paca/Moodle.

• O trabalho é individual. Entregue um arquivo tar.gz ou zip que satisfaça os seguintes requisitos:
  • O nome do arquivo deve ser da forma ep3-<seu-número-USP.tar.gz> ou ep3-<seu-número-USP.zip>. Por exemplo: ep3-12345678.zip.
  • O desempacotamento do arquivo tar.gz ou zip deve produzir um diretório com o mesmo nome do arquivo, menos o sufixo .tar.gz ou .zip. (Exemplo: ep3-12345678.) Todos os arquivos desempacotados devem estar dentro desse diretório.
  • O diretório desempacotado deve conter todos os arquivos .h ou .c necessários para gerar o programa ordena a partir do zero. Deve conter também um arquivo em formato PDF com o seu relatório. O nome desse arquivo deve ser relatorio.pdf.
  • Todos os seus arquivos .h ou .c devem ter um cabeçalho como o seguinte:

               /**********************************************************/
               /* Aluno: Fulano de Tal                                   */
               /* Número USP: 12345678                                   */
               /* Exercício-Programa 3 -- Ordenação de Arquivos de Texto */
               /* MAC122 -- BMAC -- 2008 -- Professor: Reverbel          */
               /* Compilador: ... (DevC++ ou gcc) versão ...             */
               /**********************************************************/
    

• Na correção dos EPs será usado o compilador gcc, com as opções "-Wall -ansi -pedantic -O2".
• Exercícios com erros de sintaxe (ou seja, erros de compilação) receberão nota ZERO. Seu programa deve ser compilável sem erros ou warnings, com o compilador no modo em que todos os warnings são emitidos. Caso você use o gcc, passe ao compilador (na linha de comando) as opções "-Wall -ansi -pedantic -O2". Caso você use o DevC++, clique em "Ferramentas" (ou "Tools") e "Opções do Compilador" (ou "Compiler Options") e, na tela de opções do compilador, marque como selecionada a opção "Adicione os seguintes comandos quando chamar o compilador" (ou "Add the following commands when calling compiler"). Na caixa de texto que aparece logo depois dessa opção, digite "-Wall -ansi -O2". (Não use "-pedantic" com o DevC++.)
• Seu programa deve estar bem identado, bem documentado e bem organizado. Isso será fortemente levado em conta na sua nota.
• Todos os alunos envolvidos com cola nos EPs serão reprovados na disciplina sem mais. Assim, não copie o EP de outra pessoa, nem empreste seu EP ou parte dele para ninguém. Seja cuidadoso para ninguém copie seu EP sem a sua permissão.
• Guarde com você até o final do semestre os arquivos de seus programas, pois eles podem ser solicitados pelo professor caso surja alguma dúvida.

Last modified: Sat Nov 8 18:18:20 BRST 2008