The Quick Sort Algorithm

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
  1. We set the first element of the partition as the PIVOT.
  2. We start our right scan from the next element near to pivot element.
  3. The right scan will search for number greater than or equal to pivot element.
  4. If it finds number greater than or equal to pivot element, it will set it in a box.
  5. Now left scan will start from last element of partition.
  6. Left scan will search for number less than pivot element.
  7. If it finds number less than pivot element, it will set it in a box.
  8. If the right & left scanner did not overlap or cross each other then Swap box elements.
  9. If right & left scanner overlap or cross each other then Swap PIVOT with Left scan box elements.
  10. The new position of pivot element is the proper place of that element.
    That means this element is sorted.
  11. The array on left side of sorted element is left partition.
    The array on right side of sorted element is right partition.
  12. Repeat step 1 to 13 on left partition.
  13. 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.

Click here for program code and output of Quick Sort with some Video Links as well

Quick Sort Recursive Java Program with Output and Video Links

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.


import java.io.*;
class QuickSortRecursive
{
 public static void main ( String args [] )throws IOException
 {
 int i, n=0;
 int x[] = new int[25];
 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");
 display(x,n);
 }

// my quick sort method
 static void quicksort(int x[], int lb, int ub, int n)
 {
 int j=0;

if(lb>=ub)
 return;

 j=partition(x,lb,ub,j);
 System.out.println("n After partitioning from "+(lb+1)+" to "+(ub+1)+" : n " );
 display(x,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 )
 down=down+1;

 while ( x[up] > a )
 up=up-1;

if ( down < up )
 {
 temp=x[down];
 x[down]=x[up];
 x[up]=temp;
 }
 }

 x[lb] = x[up];
 x[up] = a;

 return up;
 }

 // my display function
 static void display(int x[], int n)
 {
 int i;
 //System.out.println(" ");
 for(i=0; i<n; i++)
 System.out.print(" " + x[i]);
 System.out.println(" ");
 }
}

Check out these Video Explanations of Quick Sort. They are just so Perfect.

Click here to see complete explanation of Quick Sort Algorithm

What is the difference between Recursion and Iteration

Recursion Iteration
Definition 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.
Efficiency The recursive method are less efficient. The iterative methods are more efficient because of their execution speed.
Memory Utilization More memory is utilized in Recrusion Less memory is utilized in interation
Program Size Recursive methods give compactness to our program. Lines of code is comparatively greater in interation.
Complexity Recursion is quite complex to implement. Its less complex.

Summary :

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.