내 quickselect 알고리즘이 올바른 값을 반환하지 않습니다

Question

그래서 벡터에서 중간 값을 찾기 위해 C++에서 quickselect 알고리즘을 구현하려하지만 목록을 부분적으로 정렬하지 않고 반환하지도 않습니다 올바른 중앙값.

오류가있는 곳을 찾을 수 없습니다. 나는이 알고리즘을 처음 사용하기 때문에 구현하기 처음이다. 아래에 제 코드를 포함 시켰습니다. 그래서 나보다 더 잘 알고있는 사람이 무엇이 잘못되었는지에 대해 알고 있다면, 여러분의 의견을 진심으로 감사드립니다.

//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; 
} 

Answer 1

int pivotDist = pivotNewIndex - left + 1; 

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

이 있어야한다 또한

int pivotDist = pivotNewIndex - left; 

해야

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)])); 
}