Мой алгоритм quickselect не возвращает правильное значение

Question

Итак, я пытаюсь реализовать алгоритм quickselect в 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; 
} 

Answer 1

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