無作為抽出アルゴリズム

Question

私たちは現在アルゴリズムを研究しているので、これは宿題関連の仕事ではありませんが、この問題を「宿題」とマークしました。ちょうど安全であるように。

私たちはランダム化された選択アルゴリズムを研究しました。論理は単純なようです。リストから要素を選択し、その要素を適切な場所に配置します。インデックスの要素がその位置に来るまで、1つのサブリストでこのプロセスを繰り返します。 indexは、ソートリストで必要な要素の位置です。

これは、クイックソートアルゴリズムの変更バージョンである必要があります。しかし、私たちは一つのサブリストだけを並べ替え、両方のサブリストは並べ替えません。したがって、パフォーマンスが大幅に向上します。

私は成功し、外部記憶装置（C++、およびゼロベースの配列の）を使用して、このアルゴリズムを実装することができます。しかし、私は（インプレース）in-situで使用したアルゴリズムを実装すると、使用しないで

int r_select2(vector<int>& list, int i) 
{ 
    int p = list[0]; 

    vector<int> left, right; 

    for (int k = 1; k < list.size(); ++k) 
    { 
     if (list[k] < p) left.push_back(list[k]); 
     else  right.push_back(list[k]); 
    } 

    int j = left.size(); 

    if (j > i) p = r_select2(left, i); 
    else if (j < i) p = r_select2(right, i - j - 1); 

    return p; 
} 

を余分なサブ配列。私はこれが簡単で簡単な作業でなければならないと信じています。しかし、どこかで、現場版が間違っています。多分それはただ後半だと私は睡眠する必要がありますが、私は、次のバージョンが失敗した理由の根本的な原因を見ることができない。両方の例で

int r_select(vector<int>& list, int begin, int end, int i) 
{ 
    i = i + begin; 
    int p = list[begin]; 

    if (begin < end) 
    { 
     int j = begin; 
     for (int k = begin + 1; k < end; ++k) 
     { 
     if (list[k] < p) 
     { 
      ++j; 
      swap(list[j], list[k]); 
     } 
     } 

     swap(list[begin], list[j]); 

     if (j > i) p = r_select(list, begin, j, i); 
     else if (j < i) p = r_select(list, j + 1, end, i - j); 
    } 

    return p; 
} 

、最初の要素は、デザインを維持するために、ピボットとして使用されていますシンプル。どちらの例でも、iは私が望む要素のインデックスです。

第2の例が失敗しているアイデアはありますか？それは単なるオフ・バイ・ワンのエラーですか？

ありがとうございました！

Answer 1

これは怪しい聞こえる：

i = i + begin; 
... 
r_select(list, begin, j, i);