Tuesday, October 2, 2012

Quicksort


Quicksort is a variety of divide and conquer method. The way it works is:
  1. Choose a pivot. Pivot can be any number in the array -- your wish. You may choose, first, last or middle element or any other.
  2. Rearrange the array in such manner that elements less than the pivot lies left to it, and rest right to it. This will place pivot in the location where it should be, after the sorting is done.
  3. Repeat #1 and #2 for left part and the right part.
Assume we have array A[1..N] to be sorted.
quickSort(A, start, end)
  if start <= end
    pivot = partition(A, start, end)
    quickSort(A, start, pivot-1)
    quickSort(A, pivot+1, end)
    
partition(A, start, end)
  pivotVal = A[end]
  leftIndex = start - 1 //leftIndex is the index of the last element in left chunk
  for i = start to end-1
    if A[i] < pivotVal
      leftIndex = leftIndex + 1
      swap(i, leftIndex)
  swap(leftIndex+1, end)
  return leftIndex + 1
The quickSort routine is pretty clear. Let me explain some how partition works:
  1. We select pivot as the last element.
  2. We declared a cursor leftIndex. This cursor is our handle to the place where chunk of elements having value less than the pivot value ends. Basically this cursor is pointing last element of left sub-array. We start is just before the start.
  3. We start walking on the sub-array from left to right. If we encounter an element higher or equal to pivot, we keep moving. If we find an element that is smaller than pivot, we increase leftIndex (now leftIndex points to an element that should be in right sub-array) and we swap the current element (which is less than pivot) with leftIndex. In any case, leftIndex will point to the last of the left sub-array.
  4. When the loop ends, we will have leftIndex pointing the last element of left part of sub-array. We need to place our pivot next to it.
Complexity: The worst case complexity of quick-sort is O(n^2). However, in most practical cases, it shows complexity O(n*lg(n)). Lets see how:
WORST CASE
Assume our array is sorted in decreasing order: A[1..n] for all 1 <= i < j <= n, A[i] > A[j]
Our partition will split this into left sub-array of size 0, and right sub-array of size n-1, so,

T(n) = T(n-1) + T(0) + Θ(n)

which is same as picking the lowest from remaining array, repeating it (n-1) times. Much like selection sort. 
The above equation yields: O(n^2)
---------
TAKE A RANDOM CASE
Lets assume our pivot divides the array in 9:1 ratio, we have

T(n) = T(9*n/10) + T(n/10) + Θ(n)

if you make recursion tree, the height of tree is determined by the subtree with higher number of children. So,
The height of recursion tree will be log(10/9)(n) [log n base 10/9]
At each level we walk the sub-array which costs O(n) let assume c*n is the exact function.
So, we perform c*n operation log(10/9)(n) at max.
So, the order: O(n*log(n))

The above order stays even if for a long array the partion is 99:1.
The best case would be the one where pivot divides the array into exact halves. 
Refer:
[1] Introduction to Algorithms -CLRS, Chapter 7 Quicksort
[2] Download Java code from my GitHub repository

1 comment: