QuickSort algorithm fails due to stack overflow error in best case - C++

Question

I have a problem with the Quick Sort algorithm that I'm trying to implement.

I take a course of Fundamental Algorithms and we're provided for the laboratory assignments with pseudocode for various argorithms to implement. These algorithms are taken from Cormen and assimilated to C++ language and we're supposed to verify efficiency and generate charts for the number of assignments and comparisons within.

Now the question:

The following code is supposed to make a Quick Sort on an array of 10000 numbers and work with it in the Best Case scenario (taking the pivot of the array always at the middle):

int partition(int *a, int p, int r) {
    int x = a[r];
    countOpQS++;
    int index = p - 1;
    for (int count = p; count <= (r - 1); count++) {
        if (a[count] <= x) {
            index += 1;
            swap(a[index], a[count]);
            countOpQS += 3;
        }
        countOpQS++;
    }
    swap(a[index + 1], a[r]);
    countOpQS += 3;
    return (index + 1);
}

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 (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);
        bestQuickSort(a, p, (r - p + 1) / 2);
        bestQuickSort(a, ((r - p + 1) / 2) + 1, r);
    }
}

The call in the main function is done by:

for (index = 100; index <= 10000; index += 100) {
        countOpQS = 0;
        for (int k = 0; k < index; k++) {
            a[k] = rand();
        }
        bestQuickSort(a, 1, index);
        out3 << index << ", " << countOpQS << "\n";
    }

It should be doable with these methods, but it jumps into stack overflow pretty quickly while running. I even raised the reserved stack in Visual Studio, due to it being a necessity while going into the worst case possible (already ordered array, random pivot).

Do you guys have any idea of why it doesn't work?

Answer 1

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).