рудно переводить QuickSort с разделением Hoare на C-код, и я не могу понять, почему. Код, который я использую, показан ниже:

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,q+1,end);
    QuickSort(a,start,q);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);

        if  (i < j)
            swap(&a[i],&a[j]);
        else
            return j;
    }
}

Кроме того, я не понимаю, почемуHoarePartition работает. Может кто-нибудь объяснить, почему это работает, или, по крайней мере, связать меня со статьей, которая работает?

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

13 19  9  5 12  8  7  4 11  2  6 21

Он будет использовать pivot 13, но в итоге получит массив

 6  2  9  5 12  8  7  4 11 19 13 21 

И вернетсяj которыйa[j] = 11, Я думал, что это должно быть правдой, что массив, начинающийся в этой точке и идущий вперед, должен иметь значения, которые все больше, чем сводная, но это не так, потому что 11 <13.

Вот псевдокод для разделения Hoare (из CLRS, второе издание), если это полезно:

Hoare-Partition (A, p, r)
    x ← A[p]
    i ← p − 1
    j ← r + 1
    while  TRUE
        repeat   j ←  j − 1
            until     A[j] ≤ x
        repeat   i ←  i + 1
            until     A[i] ≥ x
        if  i < j
            exchange  A[i] ↔ A[j]
        else  return   j 

Спасибо!

РЕДАКТИРОВАТЬ:

Правильный код C для этой проблемы в конечном итоге будет:

void QuickSort(int a[],int start,int end) {
    int q;
    if (end-start<2) return;
    q=HoarePartition(a,start,end);
    QuickSort(a,start,q);
    QuickSort(a,q,end);
}

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