“Quicksort or quick-sort is a sorting algorithm. Quick sort is a divide-and-conquer algorithm. Let the list of characters be sorted by:

Q W E R T Y U I O P

The sorted list is:

E I O P Q R T U W Y

This is sort of ascending. In this article, the explanation for quicksort, sorts ascending, using the list: {“Q”, “W”, “E”, “R”, “T”, “Y”, “U”, “I”, “O”, “P”}, and the C language.”

Quick Sort in Theory

From the list, {“Q”, “W”, “E”, “R”, “T”, “Y”, “U”, “I”, “O”, “P”}, quick sort will look for a central value, called the pivot. In the sorted list,

{“E”, “I”, “O”, “P”, “Q”, “R”, “T”, “U”, “W”, “Y”}

the pivot is either “Q” or “R” since the list is even in number. If the list was odd in number, the pivot would clearly have been the middle value. “Q” at index 4 is chosen as the pivot. Remember that the list to be sorted is,

Q W E R T Y U I O P

and not the sorted list. There are 10 elements in this unsorted list.

The first stage is to look for the pivot (central value) in the unsorted list. The second stage is to place the pivot in its rightful position in the unsorted list (in this case, index 4); and put all elements that are less than the pivot on the left and all elements that are greater than the pivot on the right. The elements on the left of the pivot must not necessarily be sorted, and the elements on the right of the pivot must not necessarily also be sorted. This phase is the divide or partition phase in the divide and conquers algorithm. There are three parts for this stage: the left sub-list, the right sub-list, and the middle sub-list. The middle sub-list consists of only one element, which is the pivot. For the above-unsorted list, the result would be:

E I O P Q W R T Y U

Since the pivot is already at its final position, the last stage, in theory, is to sort the left sub-list and sort the right sub-list. This is conquering. It is a coincidence that the left sub-list, in this case, is already sorted. The right sub-list, in this case, is still to be sorted. Sorting the left and right sub-list separately, the result is:

E I O P Q R T U W Y

as required.

Quick Sort in Practice

In practice, the partitioning with some sorting (swapping) is done repeatedly in a recursive manner. That is, new smaller and smaller sub-lists are developed with their own pivots. In other words, three-part smaller and smaller sub-lists are being developed from the main list until the whole list is sorted.

There is a problem when it comes to choosing the pivot. The whole unsorted list cannot be scanned element-by-element to get the right pivot. That will be time-consuming. So an intelligent guess has to be made.

Remember that the list to be sorted is:

Q W E R T Y U I O P

Let the intelligent guess be P, the right-most element. Next, let all the elements less than P, reading from the left, go to the left of P, and let all the elements greater than P, still reading from the left, go to the right of P without conscious sorting. This gives:

E I O P Q W R T Y U

The first three sub-lists are:

{“E”, “I”, “O”}, {“P”}, {“Q”, “W”, “R”, “T”, “Y”, “U”}

P is at its rightful position (in practice, it may not necessarily be index 4; here, it is index 3 at this stage). The next step is a recursive call to divide the left sub-list into three sub-lists; and the right sub-list into three sub-lists, each with its own pivot, from an intelligent guess.

Dividing {“E”, “I”, “O”}
Let its intelligent pivot guess be, O, the right-most element. All the elements that are less than O have to go to the left, and all the elements that are greater than O have to go to the right, reading for both cases from the left. This gives:

{“E”, “I”}, { “O”}, {}

with no element on the right. If {“E”, “I”} is also recursively split, then [{“E”}, {“I”}, {}] will result. And so the first left sub-list sorted, is:

{“E”, “I”, “O”}

Dividing {“Q”, “W”, “R”, “T”, “Y”, “U”}
{“Q”, “W”, “R”, “T”, “Y”, “U”} is the first right sub-list. Let its intelligent pivot guess be U, the right-most element. All the elements that are less than U have to go to the left, and all the elements that are greater than U have to go to the right; reading for both cases, from the left. This gives:

{“Q”, “R”, “T”}, {“U”}, {“W”, “T”}

By recursively partitioning {“Q”, “R”, “T”} and {“W”, “T”} in the same way, the first right sub-list would be:

{“Q”, “R”, “T”, “U”, “W”, “Y”}

And the complete sorted list would be:

E I O P Q R T U W Y

Note that each partition does sorting in a broad sense by placing unsorted lower values on the left and unsorted higher values on the right.

Also, note that the intelligent guess was just choosing the right most element of a sub-list. That is not the best intelligent guess. On the other hand, the solution (for intelligent guess) is not to scan the whole given list! – see below for better options.

Quick Sort Code in C

Though the right-most value has been chosen for each sub-list above, conventionally, it is the left-most value that is chosen. Even when a more intelligent guess is made, the good guessed value will have to be placed in the left-most position; and the left value that was there will be placed in some other appropriate position (still in the list).

There are four C functions with the names, swap(), pivot(), partition() and quicksort(). quicksort(), the function, is coded in a recursive way, and it calls the other functions.

The swap() Function
This function swaps two array elements, using their indices. It is:

A Simple pivot() Function
This function chooses between the left-most element and the right-most element of the given whole list. It puts the lesser of either at the left-most position and the bigger at the right-most position. It is:

This is better than just choosing the right most element for the list and sub-lists, as done above. An even better pivot() function is given below.

A partition() Function
Just as the pivot() function can be written in different ways, the partition() function can be written in different ways. The one chosen for this article is:

After placing the pivot element at the left-most position of the list or sub-list, by the pivot() function, the partition function scans the list or sub-list from both ends, swapping the elements that are not on the correct side of the pivot. Scanning from the left end begins after the pivot of the left-most end (of either the list or sub-list); because the pivot will be swapped last (“do ++i;” above).

The return index, j, is the new (next) pivot position.

The quicksort() Function
This is a recursive function that calls the other functions. It is:

Here, k is the same as j returned above.

All the above functions coded together, in the order described, will form the quicksort program.

The C main Function

A suitable C main function to test the program is:

The quicksort() function proper is called from the C main function, passing the array as the first argument. The second argument left is an index, 0, of the whole list. The third argument, right, is the last-but-one index of the whole list.

Median Pivot

If three different numbers are arranged in ascending order, then the median is the middle (second) value. A better way than the previous, to obtain the pivot, is to look for the median, between the leftmost value, the middle value of the list or sub-list, and the rightmost value. The code is:

Notice that the three elements might have changed positions. This code is combined with the above pivot() function to have:

Note the last if-condition.

Conclusion

Quick-sort is a divide and conquers sorting algorithm. It keeps dividing (partitioning) the list into three sub-lists recursively. The middle sub-list always consists of one element, which is the pivot. In making the pivot, sorting is done in a broad sense in that stage. However, as the recursion continues, perfect sorting is obtained at the end of the program.