Quick Sort - for my students...

Quick Sort is a sorting algorithm where we apply Divide and Conquer policy. In this sorting algorithm, the n elements to be sorted are partitioned into three segments - a left segment, a middle segment and a right segment. The middle segment is called pivot. The middle segment exactly contains one element. The partition is done in such a way so that all the elements in the left segment have key less than the pivot and all the elements in the right segment have keys greater than the pivot. As a result, the left segment and the right segment can be sorted independently.

The basic principle of Quick sort is as follows:

• Select an element from a[0:n-1] for middle. This element is called pivot.
• Partition the remaining element in such a fashion that all elements in the left of the pivot have keys less than the pivot, and all the elements in the right segment have keys greater than the pivot.
• Sort left segment using quick sort recursively
• Sort right segment using quick sort recursively
• The answer will be left followed by middle followed by right.

The algorithm of the quick sort can be found here.

Debugging of the Algorithm of the code:

Step I: To begin with we get m = 0, n = 6, hence k = 3. After doing swap(&list[m],&list[k]), we get key = 5. The following two steps make i = 1 and j = 6.

Step II: Now the loop starts.

II while loop fails as list[i] (7) is not less than key (5). Hence i does not increase and it remains 1. The III while loop succeeds (as list[j]  > key)and hence j is decremented. So j becomes 5. In the next iteration of the III while loop, the list[j]>k condition fails, hence j remains 5 and we exit the III while loop. So we exchange list[i] and list[j] and the array becomes {5,1,8,3,2,7,9}

Next the II while loop succeeds and we increment i. Hence i becomes 2. The III while loop also succeeds and hence j becomes 4. So list[i] = list [2] = 8 and list[j] = list[4] = 2. So when we swap between list[i] and list[j], the array becomes list {5,1,2,3 8,7,9}.

Next the II while loop succeeds two times and we get i = 4. The III while loop also succeeds and we get j = 3. As j becomes larger than i, we come out of the I while loop.

Next we do swap(&list[m],&list[j]). And the list becomes list {3,1,2,5,8,7,9}

After that we recursively sort list{3,1,2}, the left segment and list{8,7,9}, the right segment.

See how all the elements of the left segment are less than 5 and all the elements in the right segment are greater than 5.

This is how we achieve the Quick Sort.