Quick Sort

Quick sort approach

Steps for quick sort algorithm

1. Start with a list of n elements
2. Choose a pivot element from the list to be sorted
3. Partition the list into 2 unsorted sublists, such that all elements in one sublist are less than the pivot and all the elements in the other sublist are greater than the pivot
4. Elements that are equal to the pivot can go in either sublist
5. Sort each sublist recursively to yield two sorted sublists
6. Concatenate the two sorted sublists and the pivot to yield one sorted list

How to pick the pivot?

There are two methods by which you can choose a pivot:

Choose randomly

The pivot can be picked randomly from the given elements. The chances of the first element being picked at every recursive call with this strategy is, $\frac{1}{n}\times\frac{1}{n-1}\times\frac{1}{n-2}\times\frac{1}{n-3}\cdots\times\frac{1}{n-n}$ ...