-1

Hoare のパーティション アルゴリズムの実装に非常に苦労しています。基本的に、私がやりたいことは、配列を 2 つの部分に分割することです。最初の部分には、指定された より小さい数値が含まれx、もう 1 つはより大きい数値が含まれます。ただし、適切な実装を理解することはできません。これは私のコードです：

void hoare(vector<int>&arr,int end, int pivot)
{
    int i = 0;
    int j = end;

    while (i < j)
    {
        while (arr[i] < pivot)
            i += 1;

        while (arr[j] > pivot)
            j -= 1;            

        swap(arr[i],arr[j]);
    }

    // return arr;
    for (int i=0; i<end; i++)
    printf("%d ", arr[i]);
}

今、私が(arr[i] <= pivot)そこに置いたものではなく、たくさんのサイトにwhileがあることがわかりました. ただし、これを行うと、次のような配列の場合:

1 3 5 7 9 2 4 6 8

私は得る：

1 3 5 4 9 2 7 6 8

しかし、私のバージョンでは、そのようなセットについては次のようになります。

12 78 4 55 4 3 12 1 0

外側のループのどちらの条件も満たされないため、プログラムはフリーズしjますi。

ピボットは、1 から数えて、配列内の特定の数値へのポインターです。たとえば、最初の例で関数に渡された数値 3 はpivotequals arr[2]、つまり 5 を意味します

それが初心者の質問であるか、すでに回答されている場合は申し訳ありませんが、私はこれに一日中費やしましたが（解決策をネットで検索しても）役に立たず、今は自殺願望があります.

前もって感謝します。

4

1 に答える 1

2

シーケンスを分割する簡単な答えは、もちろん、使用することです

auto it = std::partition(vec.begin(), vec.end(),
                         std::bind2nd(std::less<int>(), pivot));

この関数は、述語を実際には気にしませんが、シーケンスを2つのシーケンスに再配置します。1つは述語が生成するシーケンスで、trueもう1つは述語が生成するシーケンスfalseです。アルゴリズムは、イテレータを最初のサブシーケンスの最後に返します（述語が含まれる要素で構成されますtrue）。興味深いことに、アルゴリズムはフォワードイテレータで機能することになっています（ただし、実際にフォワードイテレータを取得する場合は、かなりの数のスワップを使用できます）。実装しているアルゴリズムには明らかに双方向イテレータが必要です。つまり、順方向シーケンスでも機能するという要件は無視します。

イテレータの抽象化はシーケンスアルゴリズムで非常にうまく機能するため、アルゴリズムを実装するときはまったく同じインターフェイスに従います。アルゴリズム自体は、述語が成り立たないような範囲std::find_if()のイテレータを見つけるために単純に使用します。it[begin, end)

it = std::find_if(begin, end, not1(pred));

そのようなイテレータが存在する場合、述語が成り立つようにイテレータstd::find_if()を検索するために使用されます。[std::reverse_iterator<It>(end), std::reverse_iterator<It>(it))rit

rit = std::find_if(std::reverse_iterator<It>(end), std::reverse_iterator<It>(it),
                   pred);

そのようなイテレータが存在する場合、それstd::swap()は対応する場所と更新であり、それに応じて次のbeginようendになります。

std::swap(*it, *rit);
begin = ++it;
end = (++rit).base();

itまたはritが見つからない場合、アルゴリズムは終了します。このロジックを一貫性のあるアルゴリズムに組み込むことは、かなり簡単なようです。このアルゴリズムでは、使用しようとしている演算子を使用することもできないことに注意してください。つまり、概念的には、要素はx < pivotとx >= pivot（と同じ!(x < privot)）に対してのみ比較できます。

以下の実装はテストされていませんが、完全なアルゴリズムは次のようになります。

template <typename BiIt, typename Pred>
BiIt partition(BiIt it, BiIt end, Pred pred) {
    typedef std::reverse_iterator<BiIt> RIt;
    for (RIt rit(end);
         (it = std::find_if(it, end, std::not1(pred))) != end
         && (rit = std::find_if(RIt(end), RIt(it), pred)) != RIt(it);
         ++it, end = (++rit).base()) {
         std::swap(*it, *rit);
    }
    return it;
}
于 2012-12-25T19:08:54.430 に答える