EXERCÍCIO PROGRAMA 1

Data de entrega: 8/4/2002 (tentativo)

Problema. Escreva um programa (ou vários programas) para comparar os algoritmos de ordenação vistos até agora: ordenação por inserção (nãoadaptativo e adaptativo), seleção, bolha, e por intercalação. O ideal é que você monte um esquema que torne fácil adicionar mais algoritmos para serem comparados. Por exemplo, logo estudaremos o quicksort, e então pedirei que você compare o quicksort com os demais algoritmos.

Você deve entregar não só os programas (por correio eletrônico para

yoshi@ime.usp.br e daniel@linux.ime.usp.br) como também um re-

latório com suas conclusões. Envie seu relatório eletronicamente também.

1. Para os seus testes, usem entradas de pelo menos 3 tipos: aleatórias, ordenadas (de forma crescente e de forma decrescente), “quase-orde-nadas” (você terá de pensar o que isso pode significar mais precisamente).

2. O ideal é você escrever programas para gerar também as entradas. Assim, você poderá fazer experimentos com conjuntos grandes de dados.

3. Você pode usar o comando time para determinar o tempo gasto por

um programa:

        yoshi@erdos:~$ time date
        Fri Mar  1 14:36:59 BRT 2002
        real    0m0.050s
        user    0m0.000s
        sys     0m0.000s
        yoshi@erdos:~$

4. Use o truque do o (“o pequeno”) visto em sala para contar o número de comparações e o número de atribuições de valores envolvendo os elementos sendo ordenados.

      ...
      #define o ncomps++
      int ncomps=0;
      ...
      if (o,a[j-1]>a[j])
        <troque a[j-1] e a[j]>
      ...
      <imprima ncomps>

   ...

5. Explique no relatório o funcionamento do seu sistema e discuta seus resultados.

6. Você pode olhar os exercícios 6.9 e 6.10 do Sedgewick (Algorithms in C) para conseguir mais inspiração.