False в quicksort code

Question

Я реализую quicksort, который оказался ложным. Я не могу понять, где это происходит. Я хочу реализовать версию, в которой изменение индекса i и j находится внутри while, а loop. в то время как condition.can кто-нибудь поможет мне узнать, почему этот код идет не так.

void qsort3(int *x,int l,int u){  
    if(l>=u) 
     return;  
    //swap(x[l],x[l+rand()%(u-l)]);  
    int t=x[l];  
    int i=l+1;  
    int j=u;  
    //i stop on element>=t  
    //j stop on element<=t  
    while(true){ 
     while(i<u&&x[i]<t){ 
      i++; 
     } 
     while(x[j]>t){ 
      j--; 
     } 
     if(i>=j) 
      break; 
     swap(x[i],x[j]); 
    } 
    swap(x[l],x[j]);  
    qsort3(x,l,j-1);  
    qsort3(x,j+1,u);  

}  

Я проверить этот случай, int y[]={3,4,1,10,3,2,1,1},qsort3(y,0,7), он не выйдет на самом деле, эта программа будет неправильно, если после обмена (х [г], х [у]), х [я] и х [у] оба равны , равным поворотному значению. В этом случае цикл while будет бесконечным циклом, который не будет выходить из , если я изменю while(i<u&&x[i]<=t), это будет хорошо функционировать на равном элементе.

Answer 1

Предположит, вы называете функции, как этого

int x[] = {2,3,1,4,5}; 
qsort3(x,0,4); 

так что u является инклюзивной верхней границей, так как код принимает

int j=u; 

, а затем проверяют

while(x[j]>t) 

Это означает, первый цикл должен проверить последний номер:

while(i<=u&&x[i]<t) 

Вы были i < u я был бы соблазн проверить j>0, а в следующем цикле.

EDIT

Наконец, что если у вас есть такое же число с обеих сторон перегородки, например, с {3,4,1,10,3,2,1,1}, принимая первые 3 в качестве раздела, он может застрять в цикле проверки, когда x[i] < 3 и x[j] > j и никогда не перемещать указатели, так что нам нужно

while(i<=u&&x[i]<=t) 

отделка редактировать

Как следует:

void qsort3(int *x,int l,int u){  
    if(l>=u) 
     return;  
    int t=x[l];  
    int i=l+1;  
    int j=u;  
    //i stop on element>t  
    //j stop on element<=t  
    while(true){ 
     while(i<=u&&x[i]<=t){ 
      i++; 
     } 
     while(j>0 && x[j]>t){ 
      j--; 
     } 
     if(i>=j) 
      break; 
     std::swap(x[i],x[j]); 
    } 
    std::swap(x[l],x[j]);  
    qsort3(x,l,j-1);  
    qsort3(x,j+1,u);  

}