Some of us have a mindset that quick sort is quite complicated algorithm in sorting techniques. However it is not. In this post i will explain Quick sort algorithm in detail.
The basic concept of quick sort is to pick one of the elements as the ‘pivot’ element. All other elements of the array will be rearranged by comparing with this pivot element. Everything less than the pivot element will be moved to the left of the pivot element. That means in the Left Partition. While everything greater than the pivot element will be moved to the right of the pivot element. That means in the Right Partition. Now each of these partitions are again ‘recursively’ quick sorted using the same steps.
Best Case : The quick sort algorithm acts as the fastest algorithm when middle element is chosen as the pivot element. This is because the resulting partitions are of similar size. Hence each partition will split itself into two recursively and reach the base quite fast.
Worst Case : The quick sort algorithm acts as slowest algorithm when the array is already sorted. As you can see in the picture below when array is already sorted, the depth of recursion is high.
Lets see stepwise actions for sorting 9 element array using Quick Sort
- We set the first element of the partition as the PIVOT.
- We start our right scan from the next element near to pivot element.
- The right scan will search for number greater than or equal to pivot element.
- If it finds number greater than or equal to pivot element, it will set it in a box.
- Now left scan will start from last element of partition.
- Left scan will search for number less than pivot element.
- If it finds number less than pivot element, it will set it in a box.
- If the right & left scanner did not overlap or cross each other then Swap box elements.
- If right & left scanner overlap or cross each other then Swap PIVOT with Left scan box elements.
- The new position of pivot element is the proper place of that element.
That means this element is sorted.
- The array on left side of sorted element is left partition.
The array on right side of sorted element is right partition.
- Repeat step 1 to 13 on left partition.
- Repeat step 1 to 13 on right partition.
There is one Mistake in the image above. The second line of third block says 9>=2. It is supposed to be 9>=5. Since we are comparing 9 with pivot element 5.
It took me a while to create this step wise instructions of quick sort in excel spreadsheet. I hope this makes things clear. If you get stuck somewhere, just put a comment below. I’d be glad to help you out.