Monday, 13 July 2015

Implementation in Java for Quicksort

Hello friends,

I am here with implementation of quick sort in Java. It is an divide and conquer algorithm,

Its different with merge sort as it does not require to create two temp arrays separately, instead works in place and does operations on the original array itself. It divides the work in segments and work on each segment.

It is not an stable sorting algorithm as it does not take care of preserving the relative ordering of equal elements.

Please find my implementation for the quick sort below

package com.algorithm.sorting;

public class QuickSort {
 
 public static void main(String[] args) {
  int a[] = {5,33,45454,43254,2,67,8,78,8,8,8,85654,5,4,-1,-1,1,234,24,43,4,-7,45,4,-5,544,9,8,7,6,5,4,3,2,11,2,3,4,5,6,7,8,9};
  quicksort(a);
  for(Integer i : a){
   System.out.println(i);
  }
 }

 public static void quicksort(int[] array) {
  conquerAfterDivide(array, 0, array.length - 1);
 }

 private static void conquerAfterDivide(int[] array, int start, int end) {
  if (start < end) {
   int pivotIndex = divide(array, start, end);
   conquerAfterDivide(array, start, pivotIndex - 1); // keep on dividing the left and then conquer
   conquerAfterDivide(array, pivotIndex + 1, end); // keep on dividing the right and then conquer
  }
 }
 /**Actual division of work, work is done on a segment of the array
  * 
  * @param array
  * @param start
  * @param end
  * @return pivot index
  */
 private static int divide(int[] array, int start, int end) {
  int pIndex = start; // choose start and not 0 :) as this is a common mistake , ( I made initially too )
  
  
  // below 4 line ensure to avoid the worst case (sorted array) time complexity of O(n*N)
  // choose the element at the middle as pivot and swap it with element at last 
  int mid = start + ((end-start)/2);
  int temp = array[mid]; 
  array[mid] = array[end];
  array[end] = temp;
  
  
  int pivot = array[end];
  // the motive of this for loop is to find the index
  // for the pivot element
  // i.e. pIndex = number of elements smaller than pivot element
  for (int i = start; i <= end-1; i++) {
   if (array[i] < pivot) {
    // swap & increment pIndex by 1 as one smaller element has been
    // found and has been put at left of the would be final position
    // of pivot element.
    temp = array[i];
    array[i] = array[pIndex];
    array[pIndex] = temp;
    pIndex++;
   }
  }
  // put the pivot to the correct index calculated in the for loop above
  array[end] = array[pIndex];
  array[pIndex] = pivot;

  return pIndex;
 }

}