RE: erro?

[Paulo Feofiloff <pf@ime.usp.br>]

giord@uol.com.br writes:

 >     Estava lendo as notas de aula do prof. Paulo Feofiloff sobre
 > Quicksort, quando me deparei com essa função no exercçio número 2:
 > 
 > #define troca(X, Y) { int t = X; X = Y; Y = t; }
 > 
 >           int particione (int a[], int l, int r) {
 >              int v = a[r], i = l, j = r-1;
 >              while (i <= j) {
 >                 if (a[i] < v) ++i;
 >                 else if (v < a[j]) --j;
 >                 else {
 >                    troca (a[i], a[j]);
 >                    ++i; --j;
 >                 }
 >              }
 >              // agora i == j+1
 >              troca (a[i], a[r]);
 >              return i;
 >           }
 > 
 >          Eu li esse trecho de código e não concordei com o comentário
 > que o prof. fez:  // agora i == j+1.

Certíssimo.
Para consertar a coisa eu precisaria trocar "if (a[i] < v) ++i;"
por "if (a[i] <= v) ++i;".

Eis conserto que fica mais de acordo com o Sedgewick:

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

Será que agora está certo?

PF