Quick Sort

Background

If you have not read up on how the bubble sort and insertion sort work, and understand their time efficiencies, read those sections first. An appreciation of this will help you understand the purpose behind this approach.

You should then read through how merge sort works, as quick sort is extremely similar.

How it works

As with a merge sort, the quick sort works on the ‘divide and conquer‘ principle – that is, split the data into smaller lists, sort them, and recombine.

However, the mechanism is different.

As you have seen previously, a merge sort separates the data out into smaller and smaller lists until the list length is 1. This is done by repeatedly dividing each list into two halves.

The quick sort does not implement the same division mechanism. Instead, a pivot value is chosen from within the list, and any value lower goes into list A, and any value greater goes into list B. This process may result in different length lists, as the pivot value may not be the middle-most value in a set of data.

Picking a pivot

In instances where the pivot value is the lowest or highest value in a list, the efficiency of the quick sort is reduced, as all values will fall on the same side of the pivot value. It isn’t practical to pick a ‘mid point’ value for the pivot, as you’d need to have sorted the data first to achieve this. One compromise is to pick the median of three. That is, pick three values from the list, and use the median value of the three for the pivot. Although this will not necessarily result is using a value representative of the middle of the list, it can at least greatly reduce the likelihood of using the lowest or highest value in the list, therefore improving overall efficiency.

Comparison with merge sort

For further information and a comparison of the two sorting algorithms, see this article.