Quicksort algorithm
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:
- Partition(
A[s .. e]): given an input arrayA[s .. e],choose a pivotPto rearrange the array such atelementOf(A[s .. pivotIndex])<=pivot<=elementOf(A[pivotIndex .. e]). - Call Partition(
A[s .. pivotIndex]) and Partiontion(A[pivotIndex .. e]) recursively. - The partitioning process stops when there is only one element in
ALeftorARight.
Pseudo Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void quickSort(int[] A, int start, int end){ if (start >= end) { return; } // after calling partition, A[start .. pivotIndex - 1] are not larger than A[pivotIndex] int pivotIndex = partition(A, start, end); quickSort(A, start, pivotIndex - 1); quickSort(A, pivotIndex + 1, end); } int partition(int[] A, int start, int end) { // select an pivot // rearrange A into two parts, // the elements in the left part are smaller than or equal to pivot // the elements in the right part are larger than or equal to pivot //return the index of the pivot in A } |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
public class QuickSort { void quickSort(int[] A, int start, int end){ if (start >= end) { return; } int pivotIndex = partition(A, start, end); quickSort(A, start, pivotIndex - 1); quickSort(A, pivotIndex + 1, end); } public void swap(int[] A, int i, int j) { int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } int partition(int[] A, int start, int end) { // select an pivot // rearrange A into two parts, // the elements in the left part are smaller than or equal to pivot // the elements in the right part are larger than or equal to pivot //return the index of the pivot in A Random r = new Random(); int p = start + r.nextInt(end - start + 1); swap(A, start, p); int pivot = A[start]; int left = start + 1; int right = end; while(left <= right) { while(left <= right && A[left] <= pivot) { left++; } while(left <= right && A[right] >= pivot) { right--; } if(left <= right){ swap(A, left, right); } } // now A[right] is the right most elment that is less than pivot swap(A, right, start); return right; } public static void main(String[] args) { int[] A = {1, 3, 4, 6, 7, 9, 10}; new QuickSort().quickSort(A, 0, A.length - 1); for(int i:A) { System.out.println(i); } } } |
