Prerequisites

To learn about Quick Sort, you must know:

1. Python 3
2. Python data structures - Lists
3. Recursion

What is Quick Sort?

We are in the fifth and final tutorial of the sorting series. The previous tutorial talks about Bubble Sort, Insertion Sort, Selection Sort and Merge Sort. If you haven’t read that, please do as we will be building off of those concepts. Like all sorting algorithms, we consider a list to be sorted only if it is in the ascending order. Descending order is considered the worst unsorted case.

Quick Sort is quite different and complicated from the sorting techniques we have seen so far. In this technique, we select the first element and call it the pivot. The idea is to group elements such that elements to the left of the pivot are smaller than the pivot and the elements to the right of the pivot are larger than the pivot. This is done by maintaining two pointers left and right. The left pointer points to the first element after the pivot. Let us refer to the element pointed by left as lelement. Similarly, the right pointer points to the farthest element on the right side of the list. Let us call this element as relement. At each step, compare lelement with pivot and relement with pivot. Remeber lelement < pivot and relement > pivot. If these conditions are not satisfied, the lelement and relement are swapped. Else, left pointer is incremented by 1 and the right pointer is decremented by 1. When left >= right, the pivot is swapped with either the lelement or relement. The pivot element will be in its correct position. Then continue the quick sort on the left half and the right half of the list.

Let us see this using an example, alist = [5,9,6,2,7,0]

Similarly, perform Quick Sort on the left half - [2,0] and on the right half [6,7,9]. Repeat this process until the whole list is sorted. Even though we can see that the right half is already sorted, the algorithm has no way of knowing this.

See this animation for better understanding.

How to implement Quick Sort?

Now that you have a fair understanding of what Quick Sort is, let us take a look at the algorithm and its code.

Algorithm

1. Choose a pivot
2. Set a left pointer and right pointer
3. Compare the left pointer element (lelement) with the pivot and the right pointer element (relement) with the pivot.
4. Check if lelement<pivot and relement>pivot:
   1. If yes, increment the left pointer and decrement the right pointer
   2. If not, swap the lelement and relement
5. When left >= right, swap the pivot with either left or right pointer.
6. Repeat steps 1 - 5 on the left half and the right half of the list till the entire list is sorted.

Code

def quickSort(alist):

  quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):

  if first<last:
      splitpoint = partition(alist,first,last)
      quickSortHelper(alist,first,splitpoint-1)
      quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):

  pivotvalue = alist[first]
  leftmark = first+1
  rightmark = last
  done = False

  while not done:
      while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
          leftmark = leftmark + 1

      while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
          rightmark = rightmark -1

      if rightmark < leftmark:
          done = True
      else:
          temp = alist[leftmark]
          alist[leftmark] = alist[rightmark]
          alist[rightmark] = temp

  temp = alist[first]
  alist[first] = alist[rightmark]
  alist[rightmark] = temp

  return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

Courtesy of the code is Interactive Python.

How to choose a pivot?

Choosing the pivot is very crucial as it determines the efficiency of this algorithm. If we get an already sorted list and we choose the first element as pivot then it will be a disaster! This is because there will be no element greater than the pivot and this drastically brings down the performance. To avoid this, several methods are available to select the pivot value. One such method is the median method. In this, we choose the first element, the last element, and the middle element. After comparing these three elements, we choose the one with the median value. Let us see this with an example, alist = [5,6,9,0,3,1,2]

First element is 5, last element is 2 and the middle element is 0. Comparing these values, it is clear that 2 is the median value and this selected as pivot. Methods such as this ensure that we don’t end up with the worst choice as our pivot. Remember the worst choice for pivot is the smallest or the largest value in the list.

Conclusion

Quick Sort works best with small and large number of elements. The worst case runtime complexity of Quick Sort is O(n2) similar to that of Insertion and Bubble Sort but it can be improved to O(nlog(n)) as discussed in the previous section. Unlike Merge Sort this doesn’t have the disadvantage of using extra memory or space. That is why this is one of the most commonly used sorting techniques. That’s all for this tutorial. Happy Pythoning!