Мне сложно перевести 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
он будет использовать свод 13, но в итоге получит массив
6 2 9 5 12 8 7 4 11 19 13 21
и вернет j, равный a[j] = 11.Я думал, что это должно быть правдой, что массив, начинающийся в этой точке и идущий вперед, должен иметь значения, которые все больше, чем стержень, но это не так, потому что 11 <13. </p>
Вот псевдокод дляРазделение 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;
}
}