Modifying this Quicksort to always use the last element as the pivot

Question

I have the following Quicksort that always chooses the first element of the subsequence as its pivot:

void qqsort(int array[], int start, int end) {
    int i = start; // index of left-to-right scan
    int k = end; // index of right-to-left scan

    if (end - start >= 1) { // check that there are at least two elements to sort 
        int pivot = array[start]; // set the pivot as the first element in the partition
        while (k > i) { // while the scan indices from left and right have not met, 
            while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first element greater than the pivot
                i++;
            while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first element not greater than the pivot
                k--;
            if (k > i) // if the left seekindex is still smaller than the right index, swap the corresponding elements
                swap(array, i, k);              
        }
        swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot 
        qqsort(array, start, k - 1); // quicksort the left partition
        qqsort(array, k + 1, end); // quicksort the right partition
    } else { // if there is only one element in the partition, do not do any sorting 
        return;
    }
}

Now as you can see, this algorithm always takes the first element to be the pivot: int pivot = array[start];

I want to modify this algorithm to make it always use the last element instead of the first element of the subsequence, because I want to analyze the physical running times of both implementations.

I tried changing the line int pivot = array[start]; to int pivot = array[end]; but the algorithm then outputted an unsorted sequence:

//Changes: int pivot = array[end]; 
unsorted: {5 4 3 2 1}
*sorted*: {1 2 5 4 3}

To test another pivot, I also tried using the center element of the subsequence but the algorithm still failed:

//Changes: int pivot = array[(start + end) / 2]; 
unsorted: {5 3 4 2 1}
*sorted*: {3 2 4 1 5}

---

Can someone please help me understand this algorithm correctly and tell me what changes do I need to make to successfully have this implementation always choose the last element of the subsequence as the pivot?

Answer 1

The Cause of the Problem

The problem is that you use int k = end;. It was fine to use int i = start; when you had the pivot element as the first element in the array because your checks in the loop will skim past it (array[i] <= pivot). However, when you use the last element as the pivot, k stops on the end index and switches the pivot to a position in the left half of the partition. Already you're in trouble because your pivot will most likely be somewhere inside of the left partition rather than at the border .

The Solution

To fix this, you need to set int k = end - 1; when you use the rightmost element as the pivot. You'll also need to change the lines for swapping the pivot to the border between the left and right partitions:

swap(array, i, end);
qqsort(array, start, i - 1);
qqsort(array, i + 1, end);

You have to use i for this because i will end up at the leftmost element of the right partition (which can then be swapped with the pivot being in the rightmost element and it will preserver the order). Lastly, you'll want to change k >= i to k > i in the while which decrements k or else there is small change of an array[-1] indexing error. This wasn't possible to happen before because i always at least was equal to i+1 by this point.

That should do it.

Sidenote:

This is a poorly written quicksort which I wouldn't recommend learning from. It has a some extraneous, unnecessary comparisons along with some other faults that I won't waste time listing. I would recommend using the quicksorts in this presentation by Sedgewick and Bentley.