Quick sort:

        Quick sort is the most general sorting method that is used in many programs as a subprogram as it does sorting of numbers very fast as compared to other sorting algorithms (excluding some  cases ).Of Course in some cases (for large numbers ) merge sort is better,But in general we will be using only a small range of numbers (10 to 100).

Now i will explain this quick sort with an example
Let us take a set of numbers as an array a[]
a[] ={29,13,47,25,11,3,9,37}

The main key for the quick sort function is the selection of Pivot.we can select any of these number as Pivot.Then after we sort the numbers such that, the numbers that are less than the pivot will be on the left side and greater than pivot will be on the right side.by using recursion again we will select the pivot in d left side of pivot and right side of pivot And it continues untill there is only one element which itself is the  pivot.By this time the numbers are sorted in the same array.


The main difference between the merge and quick sort is :

merge sort    quick sort
It requires extra space It doesn't require extra space(Inplace)
Time complexity-O(nlogn)  Time complexity-O(nlogn)


The worst case for this quick sort is when the elements are in sorted i.e. either in ascending or descending order.In that case the Randamised quick sort is better(selection of pivot is random)

avg/best case : O(nlogn)
worst case : O(n^2)

The link for the code in c++ is given below :

DOWNLOAD CODE HERE

The working of the code is explained in the slides.I hope u will understand it.The link for the slides is given below :

DOWNLOAD PDF HERE

Read More