Quicksort algorithm

Tags: , , ,

Quicksort is one of the most famous sort algorithms because of its average good performance. Because of its importance and popularity, it is usually asked in technique interviews. It is also important to master QuickSort as its partitioning technique can also be used to find the Kth largest or smallest element of an array in O(n) time with O(1) space complexity. 

How quickSort algorithm works

Given an array A[s ... e], a pivot is chosen to rearrange the array into two parts: ALeft and Aright. All the elements in ALeft are less than or equal to the pivot, and all the elements in ARight are larger than or equal to the pivot. The process of rearranging the array into two parts is called partitioning.

After the partitioning, for any elements in the array, if it is in the left side of the pivot, it is no larger than pivot. If it is in the right side of the array, it is no smaller than the pivot. So if we rank the elements in ALeft and ARight respectively, the elements of the whole array will be in ranked order.  

We can use the same method to partition Aleft and ARight. If the pivot is a good choose such that ALeft and ARight contains half of the elements, we divide the original problem into two subproblems with half time complexity. That’s why quikSort can have O(NlogN) time complexity in best case. 

The whole process can be described as the following process:

  1. Partition( A[s .. e] ): given an input array A[s .. e], choose a pivot P to rearrange the array such at  elementOf(A[s .. pivotIndex]) <= pivot <= elementOf(A[pivotIndex .. e]).
  2. Call Partition(A[s .. pivotIndex]) and Partiontion(A[pivotIndex .. e]) recursively.
  3. The partitioning process stops when there is only one element in ALeft or ARight.

Pseudo Code:

How to choose the pivot

The easiest method is to choose the first or last element from the array as the pivot. 

For instance, given the array {3, 4, 5, 1, 7, 2, 4, 6}, if choosing the first element (i.e., 3) as the pivot, after partitioning the array becomes: 

{1, 2, 3, 5, 7, 4, 4, 6}.

You can see, all the elements in the left of the pivot is less than 3. All the element in the right of the pivot is larger than 3

However, there can be problems if we keep choosing the first element as the pivot if the array is sorted or nearly sorted.

For instance, given the following array:

{1, 2, 3, 4, 5, 6, 7, 8},

If we choose the first element (i.e., 1) as the pivot, after partitioning, the left side is empty.  

In the next round, 2 will be chosen as the pivot, again, the left side is empty.

This will make the time complexity O(n^2). Why?

To make a divide and conquer method has O(logN) time complexity, in the divide stage,  the key is to divide the original problem into two equally subproblems. Thus we have smaller subproblems to solve. However, if one of the subproblems is similar to the original problem (i.e., unbalanced partitioning), the subproblem may have the same time complexity to the original problem.  In this case, there is no improvement in solving the subproblem. 

Ideally, the median is selected as the pivot, so we can guarantee that the left and right sides have equal number of elements. However, it is hard to find the median of an array. An alternative way is to randomly select an element as the pivot.  On average, this method can make the time complexity of QuickSort be O(NlogN). 

In summary:

choose the left most or rightmost element

The pros is that it is simple to code, but its performance will degrade to O(n^2) when the data is sorted or nearly sorted. 

Choose the pivot randomly (using built in random function):

Pros: Simple to code. Harder for someone to construct an array that will cause it to degrade to O(n^2)
Cons: Selecting a random pivot is fairly slow. Still can degrade to O(n^2).

Use the median of medians method to select a pivot

Pros: The pivot is guaranteed to be good. Quick sort is now O(n log n) worst case !
Cons: Complicated code. Typically, a lot slower than the above methods.

Java Implementation of QuickSort Algorithm

The following is the java implementation of the quickSort algorithm using random selected pivot.