Sorting algorithms 4 - Quick sort

Like merge sort, quick sort is also better than bubble,insertion and selection. Quick sort also uses divide and conqueror approach like merge sort. The basic idea behind in quick sort is that divide array using a pivot element and sort the sub arrays. Unlike merge sort, quick sort is memory wise efficient.

Process

• In step  you have the original unsorted array.
• In step 2 select a pivot element. It can be any element in the array, most probably from somewhere middle. But in this case we'll use the last element.
• Now reorganize the array such that values less than pivot is in the left side and values greater than pivot are in the right side.
• Now if you just forget about the pivot , what you have is 2 unorderes sub arrays. So you have the same problem in the step 2. So you can now use recursively do the same stpes until you have a one element. Because when you have one element it is also sorted.
• If you do this until there are no sub arrays left, that means you have a sorted array.

Quick sort - Java implementation

 
public static void quickSort(int[] a, int start,  int end)
{
  if(start < end) {
  
  int pIndex = partition (a, start, end);
  
  quickSort(a, start, pIndex- 1);
  quickSort(a, pIndex+1, end);
  }
 }

 private static int partition(int[] a, int start, int end) {
  //Pivot can be any index.
  // In this case we choose it as the final element
  int pivot = a[end];
  
  int partitionIndex = start;
  
  for(int i = start ; i<=end -1; i++)
  {
   if(a[i] <= pivot){
    int temp = a[i];
    a[i]=a[partitionIndex];
    a[partitionIndex] = temp;
    
    partitionIndex = partitionIndex + 1;
   }
   
  }
  
  int temp = a[partitionIndex];
  a[partitionIndex]=a[end];
  a[end] = temp;
  
  return partitionIndex;
  
  
 }