MAC0122  Princípios de Desenvolvimento de Algoritmos

Home  |   Fórum  |   Livros  |   WWW  |   Diário  |   Tarefas  |   Panda  |   Alunos  |   Notas

 

Quickort

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

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

ou seja, de tal modo que a[p]  a[p+1]   . . .   a[r] .   Este capítulo estuda o algoritmo Quicksort, que em geral é bem mais eficiente que os algoritmos dos capitulos anteriores.

 

Exercícios preliminares

  1. Escreva uma função que rearranje um vetor inteiro 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 em p..r?  Posso exigir a[i] == 0?
  2. [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.  Eis uma solução:

#define troca(A, B) { int t = A; A = B; B = t; } 
typedef enum {FALSE, TRUE} bool;

int particione (int a[], int p, int r) {
    int i = p-1, j = r, v = a[r], t;

    while (TRUE) { 
        do ++i; while (a[i] < v);
        do --j; while (/*X*/ p <= j && v < a[j]);
        if (i >= j) break;
        troca(a[i], a[j]);
    }
    troca(a[i], a[r]);
    return i;
}

O programa 7.2 de Sedgewick é ligeiramente mais genérico:

typedef int itemType;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { itemType 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(itemType a[], int p, int r) 
{
    int i = p-1, j = r; 
    itemType 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 i com j, 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 em 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:

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

  1. A função partition funciona corretamente quando p == r?
  2. Certifique-se de que o índice que a função partition devolve está realmente no intervalo p..r.
  3. 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;?
  4. 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) (key(A) < key(B))   por   #define less(A,B) (key(A) <= key(B))?
  5. Qual o resultado da função partition se todos os elementos do vetor são iguais?
  6. A função partition produz um rearranjo estável do vetor?
  7. Discuta e critique a seguinte versão do algoritmo da partição:
        int particione (int a[], int p, int r) {
           int b[1000], v = a[r], i = p, j = r, k;
           for (k = p; k < r; ++k) 
              if (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;
        }
    
  8. [Gries]  Discuta e critique a seguinte versão do algoritmo da partição:
        typedef enum {FALSE, TRUE} bool;
    
        int particione (int a[], int p, int r) {
           int v = a[r], i = p, j = r-1;
           while (TRUE) {
              while (a[i] < v) ++i;
              while (j >= p &&  v <= a[j]) --j;
              if (i >= j) break;
              troca(a[i], a[j]);
              ++i; --j; 
           }
           troca(a[j], a[r]);
           return j;                     
        }
    
  9. [One-sided partition]  Discuta e critique a seguinte versão do algoritmo da partição:
        int particione (int a[], int p, int r) {
           int v = a[r], i = p, 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;
        }
    
  10. Suponha dada uma lista encadeada que armazena números inteiros. Cada célula da lista tem a estrutura abaixo.
           struct celula { int chave; struct celula *prox; } ;
    
    Escreva uma função que transforme a lista em duas: a primeira contendo as células cuja chave é par e a segunda aquelas cuja chave é impar.

Algoritmo Quicksort

A função abaixo é igual à do programa 7.1 de Sedgewick. Ela usa 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(itemType 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 o 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, 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:

N2/2  comparações.

 

x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
etc.
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x

 

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. 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.

 

x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x x x x

 

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. Portanto, a figura tem lg N linhas e o processamento de cada linha consome tempo proporcional a N.  Conclusão: o número de comparações no melhor caso é

N  lg N .

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

Exercícios

  1. 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.
  2. [Sedg 7.8, p.312]   Quantas comparações a função quicksort fará se todos os elementos do vetor a[p..r] forem iguais?
  3. [Sedg 7.9, p.313]   Quantas comparações a função quicksort se cada elemento de a[p..r] tem um de dois valores possíveis?
  4. [Importante]   Quantas comparações a função quicksort fará se o vetor a[p..r] estiver em ordem crescente?
  5. [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.
  6. A função quicksort produz uma ordenação estável?
  7. [Sedg p.315, primeiro parag.]   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 (int a[], int p, int r) {
         while (p < r) {
            int i;
            i = partition(a, p, r);
            quicksort(a, p, i-1);
            p = i+1;
         } 
    }    
    

    Reescreva mais uma vez a função, 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 de execuçã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. 

  8. Suponha dada uma versão 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]  (ou seja, a[h]  a[k] para todo h em p..i e todo k em i+1..r ).   Escreva uma versão do quicksort que use essa versão 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 rearranja o vetor a[p..r], com p <= r+1,
// de modo que ele fique em ordem crescente.
//
void quicksort_i(itemType 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 do lado maior. Consequência dessa política: o tamanho da pilha nunca passa de lg N, onde N = r-p+1.

Exercícios

  1. 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.
Demonstração animada (applet) do algoritmo de Quicksort.  Essa animação foi copiada da página da disciplina COS226 do prof. R. Sedgewick (Universidade de Princeton). Todas estão no diretório http://www.cs.princeton.edu/courses/cs226/demo/sort/.
The Sorting Algorithm Demo:  animação de algoritmos de ordenação. Página de Istvan Simon na Universidade da California em Hayward. (Istvan foi professor aqui do IME-USP).
URL of this site: www.ime.usp.br/~pf/mac0122-2002/
Last modified: Fri Nov 21 08:28:00 BRST 2014
Paulo Feofiloff
IME-USP

Valid HTML 4.01 Transitional    Valid CSS!