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

Question

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

Поэтому я пытаюсь реализовать алгоритм быстрого выбора в 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;
}

1

algorithm c++quickselect quicksort search

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

0