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?

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

Solution 2

I didn't test it, but check it anyway:

this

// after the indices have crossed,
// swap the last element in the left partition with the pivot
swap(array, start, k);

probably should be

swap(array, end, i);

or something similar, if we choose end as pivot.

Edit: That's an interesting partitioning algorithm, but it's not the standard one.

Well, the pivot is fixed in the logic of the partitioning.
The algorithm treats the first element as the Head and the rest elements as the Body to be partitioned.
After the partitioning is done, as a final step, the head (pivot) is swapped with the last element of the left partitioned part, to keep the ordering.

The only way I figured to use a different pivot, without changing the algorithm, is this:

...
if (end - start >= 1) {
    // Swap the 1st element (Head) with the pivot
    swap(array, start, pivot_index);
    int pivot = array[start];
...

Solution 3

First hint: If the data are random, it does not matter, on the average, which value you choose as pivot. The only way to actually improve the "quality" of the pivot is to take more (e.g. 3) indices and use the one with median value of these.

Second hint: If you change the pivot value, you also need to change the pivot index. This is not named explicitly, but array[start] is swapped into the "middle" of the sorted subsequence at one point. You need to modify this line accordingly. If you take an index which is not at the edge of the subsequence, you need to swap it to the edge first, before the iteration.

Third hint: The code you provided is excessively commented. You should be able to actually understand this implementation.

Comments

[Andreas Grech]

I did try that combination, but it didn't work. I tried it with array[start] and also with array[end].

[NealB]

Thanks for the Sedgewick and Bentley link - great stuff.