Projeto de Algoritmos | Índice Remissivo

Quicksort: algoritmo de separação de Gries

[Enunciado]  Eis como D. Gries (The Science of Programming, 1981, pag.345) implementa o algoritmo da separação.  A função rearranja o vetor v[p..r] e devolve um elemento j do conjunto p..r tal que v[p..j-1] ≤ v[j] < v[j+1..r] :

int separa_Gries (int v[], int p, int r) {
   int c = v[p], i = p+1, j = r;  // 1
   while (true) {  // 2
      while (i <= r && v[i] <= c) ++i;  // 3
      while (c < v[j]) --j;  // 4
      if (i >= j) break;  // 5
      int t = v[i], v[i] = v[j], v[j] = t;  // 6
      ++i; --j;  // 7
   }  // 8
   v[p] = v[j], v[j] = c;  // 9
   return j;  // 10
}

Algumas perguntas que chamam a atenção para detalhes importantes:  Que acontece se executarmos a função com p igual a r?  Que acontece se eliminarmos i <= r na linha 3?  Por que não há um j >= p na linha 4?  Que acontece se escrevermos i > j na linha 5?  Que acontece se trocarmos j por i nas linhas 9 e 10?

Análise do algoritmo

Para facilitar a análise da correção, convém reescrever assim o código:

int separa_Gries (int v[], int p, int r) {
   int c = v[p], i = p+1, j = r;
   while (/*A*/ i <= j) {
      if (v[i] <= c) ++i;
      else if (c < v[j]) --j; 
      else {
         int t = v[i], v[i] = v[j], v[j] = t;
         ++i; --j;
      }
   }
   // agora i == j+1                 
   v[p] = v[j], v[j] = c;
   return j; 
}

No início de cada iteração, ou seja, a cada passagem pelo ponto A, temos a seguinte configuração:

Na penúltima passagem pelo ponto A, teremos uma das configurações a seguir:

Portanto, na última passagem pelo ponto A, valem as seguintes relações:

• i == j+1 ,
• p ≤ j ≤ r ,
• v[p+1..j] ≤ c  e  v[j+1..r] > c .

Assim,  v[p..j-1] ≤ v[j] < v[j+1..r]  na fim da execução da função, como prometido.