Quick Sort Algorithm

Quick sort is a sorting technique, widely used for sorting. It is a Divide-and-conquer approach.
The quick sort algorithm is widely used as it is space efficient, i.e it does not require additional storage space and it is sufficiently fast and quick algorithm.

Average Case Complexity :  O(n logn)
Worst Case Complexity : O(n^2)

Basic Idea :

We randomly choose a pivot element (any random element in array) then we divide the input array into three parts.
1) Left array - having all elements smaller than pivot.
2) Pivot Element
3) Right array - having all elements greater than pivot.

Then we repeat the same procedure of choosing pivot and dividing in parts and then re-applying the steps in sub parts, till we get the sub-arrays of zero size.

Pseudo code :

1) p  <--  Partition(start,end)
   01) pivot  <--  Array[start + (end-start /2)]
   02) i  <--  start
   03) j  <--  end
   04) run for loop from start to end
         repeat i <--  i+1 until Array[i] > pivot
         repeat j <--  j-1 until Array[j] < pivot
         if i < j
         then exchange Array[i] and Array[j]
         else return j

2) applyQuickSort(start, p-1)
3) applyQuickSort(p+1, end)

Java Code :

package Sorting;

public class QuickSort {

                // private static member to store input array

                private static int[] Array;

                // method to be called to Apply sort, method returns a sorted array

                public static int[] Sort(int[] array){

                                Array = array;

                                applyQuickSort(0, Array.length-1);

                                return Array;

                }

                //method quick sort which apply quicksort in input array from start to end.

                private static void applyQuickSort(int start, int end){

                                // find position such that element at this place has

                                // (all elements smaller to it at its left)  and (all elements larger to it at its right).

                                int partitionIndex = Partition(start, end);

                                // now if left divided part has some elements, apply Quick sort in that part.

                                if(start < partitionIndex-1){

                                                applyQuickSort(start, partitionIndex-1);

                                }

                                // and if right divided part has some elements, apply Quick sort in that part.

                                if(partitionIndex+1 < end){

                                                applyQuickSort(partitionIndex+1, end);

                                }

                }

                // method to partition a given subarray (Specified by start and end index),

                // into 3 parts (unsorted left array, sorted element, unsorted right array).

                public static int Partition(int Start, int end){

                                int pivot = Array[(Start + (end-Start)/2)]; //initialize pivot

                                int i = Start; //initialize i

                                int j = end;// initialize j

// run loop from start to end-1

                                for(int loop = Start; loop<end-1; loop++ ){

                                                while(Array[i] < pivot){

                                                                i++;

                                                }

                                                while(Array[j] > pivot){

                                                                j--;

                                                }

                                                //if i<j swap Array[i] and Array[j]

                                                if(i<j){

                                                                int temp = Array[i];

                                                                Array[i] = Array[j];

                                                                Array[j] = temp;

                                                }else{

                                                                break; //break for loop

                                                }

                                }//end for loop

                                return j;

                }//end partition method

}//end class