StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMy quickselect algorithm is not returning the correct value
text
Body
copied!<p>So I'm trying to implement a quickselect algorithm in C++ in order to find the median value in a vector, however it is not properly partially-sorting the list and is also not returning the correct median value. </p> <p>I can't seem to find where the error is. I'm new to this algorithm and it's my first time trying to implement it. I've included my code below so if anyone more knowledgable than me has any idea on what is going wrong, I would very much appreciate your input.</p> <pre><code>//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; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload