Hoare パーティショニングを使用した QuickSort を 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 であるため、ここではそうではありません。
Hoare パーティショニングの疑似コード (CLRS、第 2 版から) を以下に示します。
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;
}
}