MAC0122 Desenvolvimento de Algoritmos

Quickort

Este é um resumo das seções 7.1 a 7.5 do livro do Sedgewick. O assunto é o mesmo do capitulo anterior:

Problema: rearranjar um vetor a[p..r] de modo que ele fique em ordem crescente,

ou seja, de tal modo que tenhamos a[p] ≤ a[p+1] ≤ ... ≤ a[r]. Usualmente, o vetor tem mais de um elemento (ou seja, p < r), mas devemos estar preparados para o caso de um só elemento (ou seja, p == r) e mesmo para o caso de nenhum elemento (ou seja, p > r). Vamos supor que os elementos do vetor são de um tipo Item para o qual os operadores <, <=, >=, > e == estão definidos.

Este capítulo estuda o algoritmo Quicksort, que em geral é bem mais eficiente que os algoritmos elementares.

Exercícios preliminares

Escreva uma função que rearranje um vetor a[p..r] de modo que, para algum i em p..r+1, tenhamos a[p..i-1] ≤ 0 e a[i..r] ≥ 0. Não use vetor auxiliar. Procure fazer uma função rápida. Posso exigir que i esteja no intervalo p..r? Posso exigir a[i] seja 0?
[Vetor bipartido] Um vetor a[p..r] é bipartido se existe i em p..r tal que a[p..i-1] ≤ a[i] ≤ a[i+1..r]. Escreva um algoritmo que decida se um dado vetor a[p..r] é bipartido. Em caso afirmativo, o seu algoritmo deve devolver o índice i que caracteriza a bipartição.

Algoritmo da partição

O coração do Quicksort é o algoritmo da partição. Esse algoritmo rearranja os elementos de qualquer vetor a[p..r] e devolve um índice i em p..r tal que

a[p..i-1] ≤ a[i] ≤ a[i+1..r].

A expressão a[p..i-1] ≤ a[i] significa a[h] ≤ a[i] para todo h em p..i-1 . A expressão a[i] ≤ a[i+1..r] deve ser entendida de modo semelhante.

`p`				`i`					`r`
`≤ v`	`≤ v`	`≤ v`	`≤ v`	`= v`	`≥ v`	`≥ v`	`≥ v`	`≥ v`	`≥ v`

Vamos nos restringir ao caso em que p < r, embora o problema também faça sentido com p == r. Gostaríamos que i ficasse a meio caminho entre p e r, mas devemos estar preparados para aceitar os casos extremos i == p e i == r.

É fácil inventar um algoritmo que faça o serviço. Mas não é tão fácil inventar um que seja rápido. Veja o programa 7.2 de Sedgewick:

#define less(A, B) (A < B)
#define exch(A, B) {Item t = A; A = B; B = t;} 

// Recebe vetor a[p..r] com p < r.
// Rearranja os elementos do vetor e
// devolve i em p..r tal que a[p..i-1] <=
// a[i] <= a[i+1..r].
//
int partition (Item a[], int p, int r) {
   int i = p-1, j = r; 
   Item v = a[r];

   for (;;) { 
      while (less(a[++i], v)) ;
      while (less(v, a[--j])) 
         if (/*X*/ j == p) break;
      if (i >= j) break;
      exch(a[i], a[j]);
   }
   exch(a[i], a[r]);
   return i;
}

A cada passagem pelo ponto X, ou seja, imediatamente antes de comparar j com p, temos a seguinte configuração:

`p`			`i`			`j`			`r`
`≤ v`	`≤ v`	`≤ v`	`≥ v`	`?`	`?`	`≤ v`	`≥ v`	`≥ v`	`= v`

(Os índices i e j estão ambos no intervalo p..r. Fica subentendido que se j == p então, ao contrário de todos os demais casos, pode não ser verdade que a[j] ≤ v.) Em particular, na última passagem pelo ponto X temos três possibilidades:

i == j+1 ,
i == j e a[i] == v ,
i == j mas a[i] > v, donde i == p.

O número de comparações que o algoritmo executa (só estou contando as comparações entre v e elementos do vetor) é

igual ao número de elementos do vetor,

ou seja, igual a r-p+1. Logo, o algoritmo consome uma quantidade de tempo proporcional ao número de elementos do vetor.

Exercícios

A função partition funciona corretamente quando p == r?
Certifique-se de que o índice que a função partition devolve está realmente no intervalo p..r.
No código da função partition, que acontece se trocarmos exch(a[i],a[r]); return i; por exch(a[j],a[r]); return j;?
No código da função partition, mostre que a desigualdade j-i ≥ −1 é sempre verdadeira (ou seja, i não vai muito longe depois de cruzar com j). No código da função partition, que acontece se trocarmos #define less(A,B) (A < B) por #define less(A,B) (A <= B)?
Qual o resultado da função partition se todos os elementos do vetor são iguais?
A função partition produz um rearranjo estável do vetor?

Discuta e critique a seguinte versão do algoritmo da partição:

#define lesseq(A, B) (A <= B)

int particione (Item a[], int p, int r) {
   Item b[1000], v = a[r];
   int i = p, j = r, k;
   for (k = p; k < r; ++k) 
      if (lesseq(a[k], v)) b[i++] = a[k];
      else b[j--] = a[k];
   /* agora i == j */
   b[i] = v;
   for (k = p; k <= r; ++k) a[k] = b[k];
   return i;
}

[Gries] Discuta e critique a seguinte versão do algoritmo da partição:

typedef enum {FALSE, TRUE} bool;

int particione (Item a[], int p, int r) {
   Item v = a[r];
   int i = p, j = r-1;
   while (TRUE) {
      while (less(a[i], v)) ++i;
      while (j >= p &&  v <= a[j]) --j;
      if (i >= j) break;
      exch(a[i], a[j]);
      ++i; --j; 
   }
   exch(a[j], a[r]);
   return j;                     
}

[One-sided partition] Discuta e critique a seguinte versão do algoritmo da partição:

int particione (Item a[], int p, int r) {
   Item v = a[r];
   int i = p, j = r-1;
   while (i <= j) {
      if (less(a[i], v)) ++i;
      else {
         exch(a[i], a[j]);
         --j;
      }
   }
   exch(a[j], a[r]);
   return j;
}

Suponha dada uma lista encadeada que armazena ints. Cada nó da lista tem a estrutura abaixo.
```
struct nó { 
   int chave; 
   struct nó *prox; 
} ;
```
Escreva uma função que transforme a lista em duas: a primeira contendo os nós cuja chave é par e a segunda aqueles cuja chave é impar.

Algoritmo Quicksort

A função abaixo é igual à do programa 7.1 de Sedgewick. Ela implementa o algoritmo Quicksort usando a função partition definida acima.

// A função rearranja o vetor a[p..r], com
// p <= r+1, de modo que ele fique em ordem
// crescente.
//
void quicksort (Item a[], int p, int r) {
   int i;
   if (p < r) {
      i = partition (a, p, r);
      quicksort (a, p, i-1);
      quicksort (a, i+1, r);
   }
}

Note que o algoritmo deve funcionar corretamente até mesmo quando o vetor a ser ordenado está vazio, ou seja, quando p == r+1.

Quantas comparações quicksort faz entre elementos do vetor? É claro que isso depende do número N = r-p+1 de elementos do vetor. O pior caso acontece quanto partition produz, sistematicamente, uma partição desequilibrada: N-2 elementos no subvetor a[p..i-1] e 0 elementos no vetor a[i+1..r]. Nesse caso, a função partition faz N comparações para cuidar da primeira linha da figura abaixo, depois faz N-1 comparações para cuidar da segunda linha da figura, depois faz N-2 comparações para cuidar da terceira linha, etc., e finalmente faz 2 comparações para cuidar da penúltima linha da figura. Total aproximado:

N²/2 comparações.

etc.

O melhor caso acontece quanto partition produz, sistematicamente, uma partição equilibrada: aproximadamente N/2 elementos no subvetor a[p..i-1] e aproximadamente N/2 no vetor a[i+1..r]. Nesse caso, a função partition faz N comparações para cuidar da primeira linha da figura abaixo. Na segunda linha da figura, partition faz pouco menos que N/2 para cuidar do lado esquerdo e pouco menos que N/2 comparações para cuidar do lado direito. Portanto, partition faz pouco menos que N comparações no total. Agora considere a terceira linha da figura. Aqui, partition faz quatro vezes N/4 comparações, ou seja, um total de pouco menos que N comparações. Na quarta linha da figura, partition também faz menos que N comparações. E assim por diante.

Quantas linhas tem a figura? A primeira linha tem um único bloco de N elementos. A segunda linha tem dois blocos de pouco menos de N/2 elementos cada. Na terceira linha, cada bloco tem menos que N/4 elementos. Na quarta linha, cada bloco tem menos que N/8 elementos. Na quinta linha, cada bloco tem menos que N/16 elementos. E assim por diante. Logo, o número de linhas da figura não passa de lg(N). Como o processamento de cada linha consome tempo proporcional a N, o número de comparações é

N lg(N).

Este é número de comparações no melhor caso. Este é também o número médio de comparações, embora isso não seja óbvio.

Exercícios

Mostre, passo a passo, como o quicksort ordena o vetor de caracteres EASYQUESTION. Mais precisamente, mostre o estado do vetor imediatamente depois de cada execução de partition.
[Sedg 7.8] Quantas comparações a função quicksort fará se todos os elementos do vetor a[p..r] forem iguais?
[Sedg 7.9] Quantas comparações a função quicksort fará se cada elemento de a[p..r] tiver um de dois valores possíveis?
[Importante] Quantas comparações a função quicksort fará se o vetor a[p..r] estiver em ordem crescente?
[Sedg 7.5, p. 309, Quicksort] Suponha que o algoritmo Quicksort é aplicado a um vetor com N elementos distintos dois a dois. Quantas vezes, no máximo, o elemento com a maior chave muda de lugar? Justifique.
A função quicksort produz uma ordenação estável?
[Sedg p.315, primeiro parágrafo] A função quicksort pode ser reescrita de modo que ela chame a si mesma uma só vez, e não duas vezes como acima:
```
void quicksort (Item a[], int p, int r) {
   while (p < r) {
      int i;
      i = partition(a, p, r);
      quicksort(a, p, i-1);
      p = i+1;
   } 
}    
```
Reescreva a função mais uma vez adotando a política de processar imediatamente o lado menor da partição (e portanto deixar na pilha da recursão o lado maior). Esta política garante que o tamanho da pilha da recursão não passa de lg(r-p+1), pois cada subvetor na pilha será menor que a metade do subvetor que está imediatamente abaixo na pilha.
Suponha dada uma variante da função partition que funciona assim: rearranja a[p..r] e devolve um índice i tal que a[p..i] ≤ a[i+1..r]. Escreva uma versão do quicksort que use essa variante do partition. Que restrições devem ser impostas sobre i?

Versão iterativa do Quicksort

O programa 7.3 do Sedgewick é uma versão iterativa do Quicksort. Ela usa uma pilha de ints para armazenar os índices que delimitam segmentos do vetor que estão à espera de ordenação. A implementação da pilha foi omitida, mas a ideia é que

a função push põe coisas na pilha,
a função pop tira coisas da pilha,
a função stackinit cria uma pilha vazia e
a função stackempty devolve 0 se e só se a pilha não está vazia.

// A função rearranja o vetor a[p..r], com
// p <= r+1, de modo que ele fique em ordem
// crescente.
//
void quicksort_i (Item a[], int p, int r) {
   int i;
   stackinit(); 
   push(r); push(p);
   while (!stackempty()) {
      p = pop(); 
      r = pop(); 
      if (r <= p) continue;
      i = partition(a, p, r);
      if (i-p > r-i) {
         push(i-1); push(p); 
         push(r); push(i+1);
      }
      else {
         push(r); push(i+1); 
         push(i-1); push(p);
      }
   }
}

A função adota a política de colocar na pilha primeiro o lado maior do vetor e depois o lado menor. Com isso, o lado menor será processado antes que o lado maior. Consequência dessa política: o tamanho da pilha nunca passa de lg(N), onde N = r-p+1.

Exercícios

Que acontece se a função quicksort_i acima usar uma fila no lugar de uma pilha? É claro que no lugar de push usaremos uma função entra_na_fila e no lugar de pop usaremos uma função sai_da_fila.

Veja minhas notas de aula sobre o algoritmo Quicksort.