Some of us have a mindset that quick sort is quite complicated algorithm in sorting techniques. However it is not. In this post i will explain Quick sort algorithm in detail.
The basic concept of quick sort is to pick one of the elements as the ‘pivot’ element. All other elements of the array will be rearranged by comparing with this pivot element. Everything less than the pivot element will be moved to the left of the pivot element. That means in the Left Partition. While everything greater than the pivot element will be moved to the right of the pivot element. That means in the Right Partition. Now each of these partitions are again ‘recursively’ quick sorted using the same steps.
Best Case : The quick sort algorithm acts as the fastest algorithm when middle element is chosen as the pivot element. This is because the resulting partitions are of similar size. Hence each partition will split itself into two recursively and reach the base quite fast.
Worst Case : The quick sort algorithm acts as slowest algorithm when the array is already sorted. As you can see in the picture below when array is already sorted, the depth of recursion is high.
Lets see stepwise actions for sorting 9 element array using Quick Sort
We set the first element of the partition as the PIVOT.
We start our right scan from the next element near to pivot element.
Theright scan will search for number greater than or equalto pivot element.
If it finds number greater than or equalto pivot element, it will set it in a box.
Now left scan will start from last element of partition.
Left scan will search for number less thanpivot element.
If it finds number less than pivot element, it will set it in a box.
If the right & leftscanner did not overlap or cross each other then Swap boxelements.
If right& leftscanner overlap or cross each other then Swap PIVOTwith Leftscan boxelements.
The new position of pivot element is the proper place of that element.
That means this element is sorted.
The array on left side of sorted element is left partition.
The array on right side of sorted element is right partition.
Repeat step 1 to 13 on left partition.
Repeat step 1 to 13 on right partition.
There is one Mistake in the image above. The second line of third block says 9>=2. It is supposed to be 9>=5. Since we are comparing 9 with pivot element 5.
It took me a while to create this step wise instructions of quick sort in excel spreadsheet. I hope this makes things clear. If you get stuck somewhere, just put a comment below. I’d be glad to help you out.
Quick sort is quite efficient algorithm in sorting techniques. In this post i am just sharing my piece of code of quick sort program in java. In the next post i am going to go in detailed explanation regarding quick sort algorithm. In this post i have also included some video links which will help you to understand quick sort algorithm in a better way.
public static void main ( String args  )throws IOException
int i, n=0;
int x = new int;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
System.out.print(" Enter number of elements to be sorted: ");
n = Integer.parseInt(in.readLine());
System.out.println("n Enter the elements: ");
for(i=0; i<n; i++)
System.out.print(" Element at x["+(i+1)+"]=");
x[i] = Integer.parseInt(in.readLine());
quicksort(x,0,n-1,n); // calling my recursive sort method
System.out.println("n Sorted elements are: n");
// my quick sort method
static void quicksort(int x, int lb, int ub, int n)
System.out.println("n After partitioning from "+(lb+1)+" to "+(ub+1)+" : n " );
quicksort(x,lb,j-1,n); // sorting left partition
quicksort(x,j+1,ub,n); // sorting right partition
// my partition method
static int partition (int x, int lb, int ub, int pj)
int a, down, temp, up; // a is a pivot element
a = x[lb];
up = ub;
down = lb;
while (down < up)
while ( x[down] <= a && down<up )
while ( x[up] > a )
if ( down < up )
x[lb] = x[up];
x[up] = a;
// my display function
static void display(int x, int n)
for(i=0; i<n; i++)
System.out.print(" " + x[i]);
Check out these Video Explanations of Quick Sort. They are just so Perfect.
Recursion is a process of executing certain set of instructions repeatedly by calling self function or method repeatedly.
Iteration is the process of executing certain set of instruction repeatedly, without calling the self function or method.
The recursive method are less efficient.
The iterative methods are more efficient because of their execution speed.
More memory is utilized in Recrusion
Less memory is utilized in interation
Recursive methods give compactness to our program.
Lines of code is comparatively greater in interation.
Recursion is quite complex to implement.
Its less complex.
1) Recursive function – is a function that is partially defined by itself whereas Iterative functions – are loop based imperative repetitions of a process.
2) Recursion Uses selection structure whereas Iteration uses repitation structure.
3) An infinite loop occurs with iteration if the loop-continuation test never becomes false whereas infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case.
4) Iteration terminates when the loop-continuation condition fails whereas recursion terminates when a base case is recognized.
5) When using recursion multiple activation records are created on stack for each call when in iteration everything is done in one activation record.
6) Recursion is usually slower then iteration due to overhead of maintaining stack whereas iteration does not use stack so it’s faster than recursion.
7) Recursion uses more memory than iteration.
8) Infinite recursion can crash the system whereas infinite looping uses cpu cycles repeatedly.
9) Recursion makes code smaller and iteration makes code longer.
I hope this post was helpful to you guys. Please subscribe to the blog feed if you like my posts.