Разбиение QuickSort Hoare не работает

Question

Привет Я пытаюсь написать функцию разделения Hoare как 5 часов. Я прочитал this и this и даже прямо скопировал «правильную» функцию из этих вопросов, и это все равно не так близко к ответу. Вот мой «переведенный» код из книги Кормена.

int Hpartition(int A[], int p, int r){ 
int x = A[p]; 
int i = p - 1; 
int j = r + 1; 
while(true){ 
    do{ 
     j--; 
    }while(A[j] <= x); 
    do{ 
     i++; 
    }while(A[i] >= x); 
    if(i < j){ 
     swap(A[i],A[j]); 
    } 
    else 
     return j; 
} 
} 

QuickSort:

void qs(int A[],int p,int r){ 
if(p<r){ 
    int q=Hpartition(A,p,r); 
    qs(A,p,q-1); 
    qs(A,q+1,r); 
} 
} 

Главная:

int main(int argc, const char * argv[]) { 
int tab[10]; 

for(int k=0;k<10;k++){ 
    cin >> tab[k]; 
} 


qs(tab,0,9); 

for(int i=0;i<10;i++){ 
    cout << tab[i] << " "; 
} 
return 0; 
} 

Для получения этих данных:

Она производит этот результат:

Основываясь на предыдущие вопросы, касающиеся этой темы, я знаю, что могут быть некоторые ошибки в книге. Но даже когда я применяю ответы из предыдущих вопросов, это просто не сработает.

Вот алгоритм из книги:

HOARE-PARTITION(A, p, r) 
1 x = A[p] 
2 i = p - 1 
3 j = r + 1 
4 while TRUE 
5  repeat 
6  j = j - 1 
7  until A[j] <= x 
8  repeat 
9  i = i + 1 
10 until A[i] >= x 
11 if i < j 
12  exchange A[i] with A[j] 
13 else return j 

Заранее спасибо за любую помощь.

Answer 1

У вас есть 2 ошибки перевода кода из книги:

do{ 
    j--; 
    }while(A[j] <= x); 

Вы должны инвертировать это:

do{ 
    j--; 
    }while(A[j] > x); 

То же самое с:

do{ 
    i++; 
    }while(A[i] >= x); 

И еще один здесь:

qs(A,p,q-1); 
qs(A,q+1,r); 

Изменить на:

qs(A,p,q); 
qs(A,q+1,r);