Quick sort is based on divide and conquer strategy. The time complexity for quick sort in worst case in O(n²) and in average case is O(nLogn). The Space complexity is O(1). Let’s start with quick sort algorithm,
Initially we can take consider pivot element as any one of the following,
- Last element of array,
- First element of array,
- Middle element of array,
- Any random element from the array
Why do we take pivot element?
We take pivot element as a boundary, so that we can have all the elements to left of it as small than it and towards of right of it will be greater than it.
- We are taking first element as pivot element.
- Now we run two loop start and end, start one from starting index and the other from the end.
- In start loop, If we encounter any element greater than or equal to pivot then stop the start loop and run the end loop, decrement each value form the last if the value is less than pivot then stop the end loop, and Swap the elements at that positions.
- We should repeat this process until the start < end.
- After all the elements which are less than pivot are moved to left and greater are moved to the right,i.e. when the start > end just swap the pivot with the end.
- Now we have established a boundary, i.e elements towards the left are smaller than the pivot and towards right are greater than pivot
- We can repeat the same process for each subset by making a recursive call.
