Lista de exercícios para a turma do básico.

[Imre Simon <is@ime.usp.br>]

Estes exercícios não precisam ser entregues, porém a sua resolução
deverá tornar a prova da semana que vem mais amena.

Bom trabalho,

Imre Simon


=====

Exercício 6.1

[1 ponto]   Escreva uma versão recursiva do algoritmo de ordenação por seleção. 


Exercício 6.2

[1 ponto]   Escreva uma versão recursiva do algoritmo de ordenação por inserção. 


Exercício A.2

[Sedg 6.14, p.262] [2 pontos] O algoritmo de ordenação por seleção é
estável? Justifique.

Um algoritmo de ordenação é estável se não muda a ordem relativa dos
itens que têm uma mesma chave. Por exemplo, se o algoritmo transforma
um vetor como

	    88-preto     99     88-verm     88-azul     77

(estou usando cores para distinguir chaves iguais) em 

	    77     88-verm     88-preto     88-azul     99

então o algoritmo não é estável. Veja Sedgewick, p.259.


Exercício A.3

[Sedg 6.18, p.265] [2 pontos] O algoritmo de ordenação por inserção é
estável? Justifique.


Exercício 9.3

[2 pontos]   [Sedg 9.28, p.383]   Mostre que o heapsort não é estável. 


Exercício B.1

[4 pontos] Implemente e teste um programa que ordene cadeias de
caracteres (uma lista de nomes, por exemplo). Use o algoritmo de
seleção ou inserção. Inspire-se nos programas
6.11 e 3.17 do Sedgewick (e também nas idéias sugeridas pelos
programas 6.6 a 6.10).


A série 7 de exercícios referem-se ao algoritmo de partição. Mais
exercícios e até mesmo material teórico basedo no livro texto
encontra-se na página:

  http://www.ime.usp.br/~pf/mac122/aulas/quick.htm


Exercício 7.1

[1 ponto]   Discuta e critique a seguinte variante do algoritmo da partição: 

    int partition (int a[], int l, int r) {
       int b[1000], v = a[r], i = l, j = r, k;
       for (k = l; k < r; ++k) 
          if (a[k] <= v) b[i++] = a[k];
          else b[j--] = a[k];
       // agora i == j
       b[i] = v;
       for (k = l; k <= r; ++k) a[k] = b[k];
       return i;
    }


Exercício 7.2

[1 ponto]   Discuta e critique a seguinte variante do algoritmo da partição: 

    #define troca(X, Y) { int t = X; X = Y; Y = t; }
 
    int partition (int a[], int l, int r) {
       int v = a[r], i = l, j = r-1;
       while (i <= j) {
          if (a[i] < v) ++i;
          else {
             troca (a[i], a[j]);
             --j;
          }
       }
       troca (a[j], a[r]);
       return j;
    }


Exercício 7.3

[1 ponto]   Discuta e critique a seguinte variante do algoritmo da partição: 

    #define troca(X, Y) { int t = X; X = Y; Y = t; }
 
    int partition (int a[], int l, int r) {
       int v = a[r], i = l, j = r-1;
       while (i <= j) {
          if (a[j] >= v) {
             a[j+1] = a[j];
             --j;
          }
          else {
             troca (a[i], a[j]);
             ++i;
          }
       }
       a[i] = v;
       return i;
    }


Exercício 7.4

[1 ponto]   Discuta e critique a seguinte variante do algoritmo da partição: 

    #define troca(X, Y) { int t = X; X = Y; Y = t; }

    int partition (int a[], int l, int r) {
       int v = a[r], i = l, j = r-1;
       while (1) {
          while (a[i] < v) ++i;
          while (j >= l &&  v <= a[j]) --j;
          if (i >= j) break;
          troca (a[i], a[j]);
          ++i; --j; 
       }
       troca (a[i], a[r]);
       return i;                     
    }


Exercício 10.4

Mostre, passo a passo, como o quicksort ordena o vetor "EASYQUESTION". 


Exercício 10.5

Mostre, passo a passo, como o heapsort ordena o vetor "EASYQUESTION". 


Exercício D.1

[4 pontos]   Escreva uma função recursiva com protótipo 

        void mergesort(int a[], int l, int r);

que rearrange o vetor  a[l..r-1]  em ordem decrescente. 

O código da rotina de intercalação (merge) deve estar embutido na
função mergesort.  Essa rotina de intercalação deve começar com
a[l..m-1] e a[m..r-1] decrescentes e terminar com a[l..r-1]
decrescente.

Sua função pode usar um vetor auxiliar (alocado
dinâmicamente). Inspire-se no programa 8.2 do Sedgewick.