Firstly, you should know that your function select()
rearranges the elements in the range [p, r], in such a way that the element at the index-th(note that index is one-based!) position is the element that would be in that position in a sorted sequence, just as std::nth_element
does.
So when you chose the median element of the subarray by select(a, p, r, (r - p + 1) / 2);
, the index of median is based on p
.
For example: when p = 3, r = 5
, so (r - p + 1) / 2
is 1, the median would be placed in a[4]
, it means you should call the function like this: select(a, 3, 5, 2)
. And after that, you just call the bestQuickSort()
like this:
bestQuickSort(a, p, (r - p + 1) / 2); // (r - p + 1) / 2 is 1 now!
bestQuickSort(a, ((r - p + 1) / 2) + 1, r);
of course it doesn't work! The whole code for this is:
int select(int *a, int p, int r, int index) {
if (p == r) {
return a[p];
}
int q;
q = partition(a, p, r);
//countOpQS++;
int k = q - p + 1;
if(k== index)
return a[q];
else if (index <= k) {
return select(a, p, q - 1, index);
} else {
return select(a, q + 1, r, index - k);
}
}
void bestQuickSort(int *a, int p, int r) {
if (p < r) {
select(a, p, r, (r - p + 1) / 2 + 1); // the index passed to select is one-based!
int midpoint = p + (r - p + 1) / 2;
bestQuickSort(a, p, midpoint - 1);
bestQuickSort(a, midpoint + 1, r);
}
}
BTW, your version of quicksort didn't always run in best case, though every time you choose the exact median of the (sub)array, but the time complexity of select
is not always O(n) since you simply choose the a[r]
as the pivot, the worst-case performance of select
is quadratic: O(n*n).