1

Hoare パーティションをクイックソートに実装する作業を行っています。私はホーレ分割を完全に理解しようとしていますが、本はすべてを説明しているわけではありません. 主に、 while TRUE 部分が何を意味するのか疑問に思っていますか? 本からの抜粋は以下です。while の部分を Java に入れるとしたら、何を使用し、その理由は何ですか?

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 < l
           exchange A[i] with A[j]
        else return j
4

2 に答える 2

2

上記のアルゴリズムに対して次のコードを試してください。

int HoarePartition (int a[],int p, int r) 
{
    int x=a[p],i=p-1,j=r+1;
    while (true) 
    {
        while (a[j] <= x) j--; 
        while (a[i] >= x) i++;
        if  (i < j) swap(a[i],a[j]);
        else return j;
    }
}
于 2013-02-28T04:48:07.600 に答える