1

そのため、ベクトル内の中央値を見つけるために C++ でクイック選択アルゴリズムを実装しようとしていますが、リストを適切に部分的にソートしておらず、正しい中央値も返していません。

エラーがどこにあるかを見つけることができないようです。私はこのアルゴリズムを初めて使用し、それを実装しようとするのは初めてです。以下に私のコードを含めましたので、私よりも知識のある人が何がうまくいかないのかについて何か考えを持っているなら、私はあなたの意見に非常に感謝しています.

//Returns the index of the object with the kth largest value
int QuickSelect(vector<Object *> & list, int left, int right, int k){

    /*-Base case-*/
    if(left == right) /*List only contains a single element*/
        return left; /*Return that index*/

    int pivotIndex = left + (rand() % (int)(right - left + 1));
    int pivotNewIndex = Partition(list, level, left, right, pivotIndex);
    int pivotDist = pivotNewIndex - left + 1;

    if(pivotDist == k)
        return pivotNewIndex;
    else if (k < pivotDist)
        return QuickSelect(list, level, left, pivotNewIndex-1, k);
    else
        return QuickSelect(list, level, pivotNewIndex+1, right, k-pivotDist);
}


int Partition(vector<Object *> & list, int left, int right, int pivotIndex){

    int pivotValue = list.at(pivotIndex)->value;
    std::swap(list[pivotIndex], list[right]);
    int storeIndex = left;
    for(int i = left; i < right; i++){
        if(list.at(i)->value < pivotValue){
            std::swap(list[storeIndex], list[i]);
            storeIndex++;
        }
    }
    std::swap(list[right], list[storeIndex]);
    return storeIndex;
}
4

1 に答える 1

0 
int pivotDist = pivotNewIndex - left + 1;

する必要があります

int pivotDist = pivotNewIndex - left;

また

return QuickSelect(list, pivotNewIndex+1, right, k-pivotDist);

する必要があります

return QuickSelect(list, pivotNewIndex+1, right, k-pivotDist-1);

私のテストコードは次のとおりです。

int main() {
  int d[] = {0, 1, 2, 3, 4};

  do {
    std::vector<Object*> v;
    v.push_back(new Object(d[0]));
    v.push_back(new Object(d[1]));
    v.push_back(new Object(d[2]));
    v.push_back(new Object(d[3]));
    v.push_back(new Object(d[4]));

    for (int i = 0; i < v.size(); ++i) {
      std::cout << v[i]->value << " "; }
    std::cout << std::endl;

    int n = QuickSelect(v, 0, 4, 2);

    if (v[n]->value != 2) {
      std::cout << "error: ";
      for (int i = 0; i < v.size(); ++i) {
        std::cout << v[i]->value << " "; }
      std::cout << std::endl;
    }
  }
  while (std::next_permutation(&d[0], &d[sizeof(d)/sizeof(int)]));
}
于 2013-10-04T03:09:43.757 に答える