Quick Sorting – A complete analysis with c/c++ and JAVA

Quick Sorting is a Divide and Conquer sorting method.
Before going ahead, let’s take an example to understand the divide and conquer method.

Quick Sorting with a real life example

There are 10 balls, all with different weight. Arrange them in ascending order of their weight.

Approach:
Step 1: Arrange all the balls in a line.
Step 2: Take out 1^st ball, and mark it as reference ball.
Step 3: Arrange balls so that, left of reference ball are lighter balls and right of it are heavier balls (order doesn’t matter).
Note:The number of comparisons should be minimum.

One way to do is having two markers: i- is denoting lighter balls and j- is for heavier balls than reference ball.
Sub-Step 3.1: i will start from next to reference ball and keep on moving to right until a heavier ball is found than the reference ball.
Sub-Step 3.2: Similarly, j will start from another side (right most here) and keep on moving to left until a smaller ball is found.
If i < j following may be the situation:
So, swap the i^th and j^th balls [ note that the value of i and j remains same]
Now following may be the situation:
While i < j, go to Sub-Step 3.1
Sub-Step 3.3: Swap j^th and reference balls

Step 4: Now you have two groups: group 1 and 2. Go to step 2 until each group left out with two balls.

In action:

Step 1:


Step 2:


Step 3:


Sub-Step 3.1


Now, i will not move further.

Sub-Step 3.2:

Now i^th and j^th values are required to be swapped



Note: still i and j can move further. Go to Sub-Step 3.1:

Sub-Step 3.2:



Still i < j, Go to Sub-Step 3.1:

Sub-Step 3.2:




Now, the condition until(i<j) does not satisfy anymore
Sub-Step 3.3:


Step 4: Two groups are formed now:


Go to Step 2, for both the groups.

Hint: for group 1 now the reference ball will be 7 (reference_ball =0) and the i = 1 (reference_ball+1), and j=j-1 , that is 3.
For group 2, reference ball will be 50 and the i = i, that is 5, and j =last, that is 8.

Quick Sorting implementation in C/C++

#include<stdio.h>
void quickSort(int ball[], int i, int j) {
      int tmp;
      int left=i;
      int right = j;
      int reference_ball = i;
      while (i <= j) {
            while (ball[i] < ball[reference_ball])
                  i++;
            while (ball[j] > ball[reference_ball])
                  j--;
            if (i <= j) {
                  tmp = ball[i];
                  ball[i] = ball[j];
                  ball[j] = tmp;
                  i++;
                  j--;
            }
      }
      if (left < j)
            quickSort(ball, left, j);  //for group 1 (left portion)
      if (i < right)
            quickSort(ball, i, right); //for group 2 (right portion)
}

int main()
    {
      int ball[]={2,4,3,8,1,5};
      int p;
      printf("The original array is:\n");
      for(p=0;p<6;p++)
         {
           printf("%d, ",ball[p]);
         }
      quickSort(ball,0,5);
      printf("The sorted array is:\n");
      for(p=0;p<6;p++)
         {
           printf("%d, ",ball[p]);
         }
    return 0;
    }

Quick sorting implementation in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;

class SK {
    public static void quickSort(int ball[], int i, int j) {
      int tmp;
      int left=i;
      int right = j;
      int reference_ball = i;
      while (i <= j) {
            while (ball[i] < ball[reference_ball])
                  i++;
            while (ball[j] > ball[reference_ball])
                  j--;
            if (i <= j) {
                  tmp = ball[i];
                  ball[i] = ball[j];
                  ball[j] = tmp;
                  i++;
                  j--;
            }
      }
      if (left < j)
            quickSort(ball, left, j);  //for group 1 (left portion)
      if (i < right)
            quickSort(ball, i, right); //for group 2 (right portion)
    }

	public static void main (String[] args) {
	  int ball[]={2,4,3,8,1,5};
      int p;
      System.out.println("The original array is:\n");
      for(p=0;p<6;p++)
        {
         System.out.println(ball[p]);
        }
      quickSort(ball,0,5);
      System.out.println("The sorted array is:\n");
      for(p=0;p<6;p++)
        {
         System.out.println(ball[p]);
        }
        
	}
}

Do you want to practice more programming question??? Click Here.