What is QuickSort?
1.) It is divide-and-conquer algorithm
2.) It sorts “in place”(like insertion sort, but not like merge-sort).
How to apply QuickSort on an array of n-emelents?
a.)Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray.
b.)Conquer: Recursively sort the two subarrays.
c.)Combine: This is a trivial step.
Key : Linear-time partitioning subroutine.
Lets check out how the partitioning subroutine works
Partitioning Subroutine
Partition(A,p,q) … A[p...q]
x <– A[p] ..here we assume pivot = A[p]
i <– p
for j <– p+1 to q
do if A[j] ≤ x
then i <– i+1
exchange A[i] <–> A[j]
exchange A[p] <–> A[i]
return i
Running time of Partitioning subroutine : θ(n) for n elements.
Now as we know the partitioning subroutine, we will write the pseudocode for Quicksort
Pseudocode
QuickSort(A,p,r)
if(p<r)
then q <– Partition(A,p,r)
QuickSort(A,p,q-1)
QuickSort(A,q+1,r)
Initial Call : QuickSort(A,1,n)
Running time of QuickSort
| Worst case performances | Θ(n2) |
| Best case performance: | Θ(nlogn) |
| Average case performance: | Θ(nlogn) comparisons |
Program
I tried to implement this in Java, feel free to use the code and let me know your inputs if this program can be improved.
package com.bundle.algos;
public class QuickSort {
public static void main(String args[]){
//int[] _array = new int[]{6,10,13,5,8,3,2,11};
int[] _array = new int[]{2,6,5,7,8,9,3,4};
if(_array.length == 0){
System.out.println(“Empty Array”);
System.exit(0);
}else if(_array.length == 1){
System.out.println(“Only one element, Array already sorted”);
}else{
quickSort(_array,0,_array.length -1);
}
for(int i=0;i<=_array.length-1;i++){
System.out.println(_array[i]);
}
}
public static void quickSort(int[] input, int p,int r){
if(p < r){
int q = partition(input,p,r);
//System.out.println(“i=” + q);
//System.out.println(“Value=” + input[q]);
quickSort(input,p,q-1);
quickSort(input,q+1,r);
}
}
public static int partition(int[] input,int p, int q){
int x = input[p];
int i = p;
for(int j = (p+1);j <= q;j++){
if(input[j]<= x){
i = i + 1;
int temp = input[j];
input[j] = input[i];
input[i] = temp;
}
}
int temp1 = input[p];
input[p] = input[i];
input[i] = temp1;
return i;
}
}
Worst cases
a.) Input sorted or reverse sorted
b.) Partition around min or max element.
c.) One side of partition always has no elements
Best cases(intuition only)
a.) Partition splits the array evenly(same as merge sort).
