Projeto de Algoritmos | Índice Remissivo

Outras versões do Quicksort

[Enunciado]  O algoritmo Quicksort pode ser implementado de várias outras maneiras além da discutida na página Quicksort. A diferença entre as várias versões está no modo de formular o problema da separação.  Em todas as versões abaixo, o mecanismo de controle da altura da pilha de execução foi omitido para tornar o código mais legível.

Em todas as versões, usaremos a macro parametrizada

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

para trocar os valores de dois elementos de um vetor.

Versão A

A versão abaixo usa uma formulação do problema da separação quase igual à que adotamos na página Quicksort: rearranja v[p..r] de modo que tenhamos  v[p..j-1] ≤ v[j] ≤ v[j+1..r]  (note o segundo ≤)  para algum j em p..r.

// A função rearranja o vetor v[p..r]
// em ordem crescente.

void quick_FlipFlop (int v[], int p, int r) {
   if (p < r) {      
      int j = p, k = r, ff = -1;
      while (j < k) {
         if (v[j] > v[k] {
            troca (v[j], v[k]);
            ff = -ff;
         }
         if (ff == -1) --k;
         else ++j;
      }
      quick_FlipFlop (v, p, j-1);
      quick_FlipFlop (v, j+1, r);
   }
}

Versão B

A versão seguinte (veja livro de Cormen, Leiserson e Rivest) usa a primeira das duas formulações do problema da separação mencionadas na página Quicksort : rearranja v[p..r] de modo que  v[p..j] ≤ v[j+1..r]  para algum j em p..r-1:

// A função rearranja o vetor v[p..r]
// em ordem crescente.

void quick_CLR (int v[], int p, int r) {
   if (p < r) {      
      int i = p-1, j = r+1, c = v[p];
      while (true) {
         do --j; while (v[j] > c);
         do ++i; while (v[i] < c);
         if (i >= j) break;
         troca (v[i], v[j]);
      }
      quick_CLR (v, p, j);
      quick_CLR (v, j+1, r);
   }
}

Versão C

Eis outra versão (se não me engano, ela está no livro de Sedgewick):

// A função rearranja o vetor v[p..r]
// em ordem crescente.

void quick_S (int v[], int p, int r) {
   if (p < r) {      
      int i = p, j = r, c = v[(p+r)/2];
      while (i <= j) {
         while (v[i] < c) ++i;
         while (c < v[j]) --j;
         if (i <= j) {
            troca (v[i], v[j]);
            ++i, --j;
         }
      }
      quick_S (v, p, j);
      quick_S (v, i, r);
   }
}

Exercício: formule com precisão o problema da separação que essa versão resolve.

Versão D

A seguinte versão do Quicksort é sugerida no livro de Sedgewick:

void quick_S2 (int v[], int p, int r) {
    if (p < r) {
       int i = p-1, j = r, c = v[r];
       while (1) { 
           while (v[++i] < c) ;
           while (c < v[--j]) if (j == p) break;
           if (i > j) break;
           troca (v[i], v[j]);
       }
       troca (v[i], v[r]);
       quick_S2 (v, p, j);
       quick_S2 (v, i+1, r);
    }
}

Exercício: formule com precisão o problema da separação que essa versão resolve.