Terceira Lista de Exercicios

Do livro texto (Ziviani): Cap. 3, exercícios 7, 8, 10, 11.

Exercícios extras:

1) Liste as principais vantagens e desvantagens de cada um dos métodos
vistos até o momento: inserção, seleção, bolha, shellsort, quicksort, 
heapsort e mergesort.

2) Que algoritmo de ordenação você usaria para cada um dos seguintes
casos:

  a: A ordenação original de elementos com chave idêntica precisa ser
     mantida.
  b: O tempo de execução não deve apresentar grandes variações para
     nenhum caso.
  c: A lista a ser ordenada já está sempre bem próxima da ordem final
  d: Os elementos a serem ordenados são muito grandes se comparados
     ao tamanho das chaves.
  e: A lista a ser ordenada não cabe na memória principal.

3) Ordene as letras da palavra Exemplar utilizando cada um dos métodos
estudados. Para fins de ordenação, letras maiúsculas e minúsculas devem
ser consideradas equivalentes, isto é, ``E'' e ``e'' devem ser
consideradas iguais durante comparações. Para verificar o correto andamento
de cada algoritmo, escreva o conteúdo do vetor a cada passo intermediário,
conforme as exigências abaixo. A cada caso, um exemplo com a sequência
``UMDOIS'' é mostrado.

  a: SELEÇÃO: Liste o vetor a cada elemento que atinja sua posição
              definitiva:
                             UMDOIS  Início
                             DMUOIS  D selecionado
                             DIUOMS  I selecionado
                             DIMOUS  M selecionado
                             DIMOUS  O selecionado
                             DIMOSU  S selecionado

  b: INSERÇÃO: Liste o vetor a cada elemento que é incluido na ordenação
               parcial até o momento.

                             UMDOIS Início, ordem parcial contém apenas U
                             MUDOIS Ordem parcial é MU
                             DMUOIS Ordem é DMU
                             DMOUIS         DMOU
                             DIMOUS         DIMOU
                             DIMOSU

  c: QUICKSORT: Use o elemento à esquerda da partição como pivot. Liste
                o vetor a cada nova partição (c/ dois ou mais elementos)
                completada.

                             UMDOIS Início, pivot = U
                             SMDOIU Partição SMDOI, pivot = S
                             IMDOSU Partição IMDO,  pivot = I
                             DMIOSU Partição MIO,   pivot = M
                             DIMOSU Partição MO,    pivot = M
                             DIMOSU

  d: QUICKSORT: Use o elemento no centro da partição como pivot ((esq+dir)/2).
                Liste o vetor a cada nova partição (c/ dois ou mais elementos)
                completada.

                             UMDOIS Início, pivot na pos.3 ((1+7)/2) = D
                             DMUOIS Partição MUOIS, pivot = O
                             DMIOUS Partição MI,    pivot = M
                             DIMOUS Partição US,    pivot = U
                             DIMOSU 

  e: HEAPSORT: Liste o vetor a cada elemento que é inserido no heap na fase
               de construção e a cada elemento que é removido, antes e depois
               do heap ser refeito.
                             
                             UMDOIS Início, head 4-6 OK
                             UMSOID D adicionado ao heap
                             UOSMID M adicionado
                             UOSMID U adicionado, heap completo
                             DOSMIU U removido e trocado com D
                             SODMIU heap refeito
                             IODMSU S removido, trocado com I
                             OMDISU heap refeito
                             IMDOSU O removido, trocado com I
                             MIDOSU heap refeito
                             DIMOSU O removido, trocado com D
                             IDMOSU heap refeito
                             DIMOSU I removido, trocado com I 
                             
4) Para cada um dos algoritmos abaixo, dê um exemplo de sequência a ser
   ordenada que mostre que o algoritmo não é estável (dica: exceto para
   o shellsort, sequências de três elementos são suficientes):

   a: Seleção      b: Quicksort     c: Heapsort 

5) Explique quais as otimizações possíveis ao se combinar as sequintes
   técnicas:

   a: Ordenação por inserção e pesquisa binária
   b: Ordenação por inserção e listas com apontadores
   c: Quicksort e inserção
   d: Compare a: e b: