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.