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

Ankur Kulhari

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 1st 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 ith and jth 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 jth 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 ith and jth 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]);
}

}
}
```