Partially Sorted Quicksort

Question

I want to modify quicksort to where I only sort the top median items. So a set as such [9 5 7 1 2 4 6] where 5 is the median, the partially sorted set would be something like [1 2 4 5 9 6 7].

template <class Comparable>
void objectSwap(Comparable &lhs, Comparable &rhs) {
    Comparable tmp = lhs;
    lhs = rhs;
    rhs = tmp;
}

template <class Comparable>
void choosePivot(vector<Comparable> &a, int first, int last) {
    int middle = (first + last) / 2;
    objectSwap(a[first], a[middle]);
}

template <class Comparable>
void partition(vector<Comparable> &a, int first, int last, int &pivotIndex) {
    // place the pivot in a[first]
    choosePivot(a, first, last);
    Comparable pivot = a[first];
    int lastS1 = first;
    int firstUnknown = first + 1;

    for (; firstUnknown <= last; ++firstUnknown) {
        if (a[firstUnknown] < pivot) {
            ++lastS1;
            objectSwap(a[firstUnknown], a[lastS1]);
        }
        // else item from unknown belongs in S2
    }
    // decide a new pivot
    objectSwap(a[first], a[lastS1]);
    pivotIndex = lastS1;
}

template <class Comparable>
void partialsort(vector<Comparable> &a, int first, int last) {
    int pivotIndex;

    if (first < last) {  
        partition(a, first, last, pivotIndex);
        partialsort(a, first, pivotIndex - 1);
        partialsort(a, pivotIndex + 1, last);
    }
}

template <class Comparable>
void partialsort(vector<Comparable> &a) {
    partialsort(a, 0, a.size() - 1);
}

I've been watching the analysis of quicksort on youtube by mycodeschool (let me know of any other good videos, if you know any!), and I'm pretty sure I only need to change the partialsort(vector, int, int) method.
My first reaction is to think of it like mergesort, take an empty array, and stop the algorithm once length/2 has been filled. But I know that isn't how quicksort works. All the recursive calls and how first, last, and pivot always change, make it hard for me to keep track of what's going on. I'm also unsure of how I would know when I have the median. This is a homework question, so if anyone just has tips as to how I should approach this or resources that would help me better understand quicksort, I'd greatly appreciate it. Just knowing how to change it won't do me much good in better understanding the algorithm.
Sorry if it sounds like I'm being entitled to what kind of help I want!

Could you clarify whether you need at least the first half sorted or exactly the first half? Also, if you care about the second half, do you need it to be stable? Your example indicates you don't, but it would help if you made that explicit. — Ulrich Eckhardt
Essentially the first half. So everything that comes before the median needs to be sorted: So a set as such [9 5 7 1 2 4 6] where 5 is the median, the partially sorted set would be something like [1 2 4 5 9 6 7]. — user6276809
So, sorting the whole sequence would be okay, too? That would then be the simplest solution you're looking for? Anyhow, here's two approaches: First is to find the median, partition by that median and then sort the first partition. Second is to run a Quick Sort-like algorithm that simply doesn't recurse into the partitions that start beyond the median. — Ulrich Eckhardt

Jfevold Jfevold · Accepted Answer · 2016-05-01T04:15:53

It's a divide-and-conquer algorithm, so you can skip any partition which is entirely behind the middle position of the array, which will naturally hold the median value once the first half is sorted.

Partially Sorted Quicksort

1 Answers