Quick Sort

Introduction:

        It is an Algorithm of sorting taking O(nlog(n)) time to sort. This can be better understand by recursion like in merge sort. In this algorithm we take pivot and put it at its correct position after sorting its left and right side. A partition function return position of pivot in an array after placing all the smaller element left and all the larger right. Apply Quick sort to both side of pivot position.

The steps of implementation of Quick Sort are as follows:

1. Select a pivot (here we select last element)\
2. Take two pointer pointing to first element
3. Traverse the array by using 2nd(anyone) pointer
4. During the traversal:
1. If value of 2nd pointer is greater than pivot, increase 2nd pointer by 1
2. Else swap with 1st pointer also move 1st and 2nd pointer by one
5. When 2nd pointer reach to pivot swap 1st pointer with pivot
6. Apply same with left and right of pivot

Let us take an example of an unsorted array and apply Quick Sort:

    Step 1: Select a pivot, let last element be pivot

    Step 2: Take two pointer pointing to first element

    Step 3: Traverse the array using p2

    Step 4: Increase p1 when value at p2 < pivot

    Step 5: 2nd pointer reach to pivot, so swap p1 and pivot

Now all element of left is smaller and right is greater than 80

Apply Quick sort to left and right:

    As left side only one element so sort right

    We are taking last element as pivot

This is the final array