Quick sort works on the principle of divide and conquer.
Divide the list in 2 sub-lists, find a pivot element such that its actual position divides the list further in 2 lists.
So the pivot element resides at its actual position and then recursively find location of other elements. At the end of processing each element will get its actual(sorted) position and array will be sorted.
Algorithm QuickSort:
1. QuickSort(Arr, p, r)
2. if(p < r)
3. q=findPivot(Arr,p,r); //find pivot and its location [ takes O(n) ]
4. QuickSort(Arr, p,q-1); //left sub array
5. QuickSort(Arr, q+1,r); // right sub array Algorithm for partition to find pivot
Algorithm for partition to find pivot :
PARTITION (Arr, p, r )
1. x =A[r]
2. i = p-1
3. for j =p to r-1
4. if A[j] <= x
5. i=i+1
6. exchange A[i] with A[j]
7. exchange A[i+1] with x
8. return i+1
Following program implements Quick sort in java.
/**
* @author vikky.agrawal
*
*/
public class QuickSort {
int[] arr;
QuickSort(){
arr=new int[] { 5, 3, 1, 2, 9, 8 };
}
/**
* @param args
*/
public static void main(String[] args) {
QuickSort obj = new QuickSort();
obj.operate();
}
public void operate(){
System.out.println("Array before sortings: ");
printArray();
quickSort(arr,0,5);
System.out.println("Sorted array : ");
printArray();
}
public void quickSort(int[] arr, int p, int r){
if(p<r){
int q= findPivot(arr,p,r);
quickSort(arr, p, q-1);
quickSort(arr, q+1, r);
}
}
/**
* Algorithm for partition to find pivot
*
* PARTITION.A;p;r
* 1 x =A[r]
* 2 i = p-1
* 3 for j =p to r-1
* 4 if A[j] <= x
* 5 i=i+1
* 6 exchange A[i] with A[j]
* 7 exchange A[i+1] with x
* 8 return i+1
*/
public int findPivot(int[] arr, int p, int r){
int x=arr[r];
int i=p-1;
for(int j=p ;j<r; j++){
if(arr[j]<= x){
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
arr[r]=arr[i+1];
arr[i+1]=x;
return i+1;
}
public void printArray(){
for (int a : arr) {
System.out.print(a + " ");
}
System.out.println();
}
}
Complexity analysis:In average case scenario each problem is divided in 2 sub problems, hence total time required will be:
T(n)= 2T(n/2)+O(n) where O(n) is to find pivot and its location.
Using Master theorem solution to above equation comes as O(n logn)(Avg case)
In worst case scenario array may be divided in (1, n-2) in that case total time required will be
T(n)= T(1)+T(n-2)+O(n) and solution to this equation becomes : O(n^2) (Worst case)
But worst case is rare in quick sort and analysis shows that mostly average case occurs with complexity O(n logn).
For more analysis check wiki: Quicksort#analysis
Facts:
1. Worst case for quick sort occurs when array is already sorted.
2. Worst case also occurs when all the elements are same.
3. Quick sort gives better results than Mergesort in average case.
