QuickSort Algorithm

Quick sort is a comparison sort. The working of  quick sort algorithm is depending on a divide-and-conquer strategy. A divide and conquer strategy is  dividing  an array  into two sub-arrays. Quick sort is one of the fastest and simplest sorting algorithm. The complexity of quick sort in the average case is  Θ(n log(n)) and in the  worst case is Θ(n2).

In quick sort algorithm pick an element from array of elements. This element is called the pivot. Then compare the the values from left to right until a greater element is find then swap the values. Again start comparison from right with pivot. When lesser element is find then swap the values. Follow the same steps until  all elements which are less than the pivot come before the pivot and all elements greater than the pivot come after it. After this partitioning, the pivot is in its last position. This is called the partition operation. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

Pros

• Extremely fast on average

Cons

• Fairly tricky to implement and debug
• Very slow in the worst case (but see notes)
• In the worst case, could cause a stack overflow

Example:
 
Input:12 9 4 99 120 1 3 10 13




Output:1 3 4 10 12 13 99 120

public class QuickSort{
  public static void main(String a[]){
    int array[] = {12,9,4,99,120,1,3,10,13};
    quick_srt(array,0,array.length-1); 
  }
  public static void quick_srt(int array[],int low, int n){
     int lo = low;
     int hi = n;
     if(lo >= n) {
       return;
     }
     int mid = array[(lo + hi) / 2];
     while(lo < hi) {
         while(lo<hi && array[lo] < mid) {
            lo++;
         }
         while(lo<hi && array[hi] > mid) {
            hi--;
         }
         if(lo < hi) {
            int T = array[lo];
            array[lo] = array[hi];
            array[hi] = T;
         }
     }
     if(hi < lo) {
        int T = hi;
        hi = lo;
        lo = T;
     }
     quick_srt(array, low, lo);
     quick_srt(array, lo == low ? lo+1 : lo, n);
  }
} 

Notes: If the middle element in the array is very large or very small, the sort becomes slower. To reduce the chances of this, you can take median of the first, middle and last elements and put it in the middle. In a degenerate case, Quick sort could also recurse to a very deep level and cause a stack overflow. One way to avoid this is to keep track of the level of recursion (e.g. by passing it as a parameter) and switch to a simpler sort (like selection sort) if the recursion is too deep.

Reference: roseindia