3,1,4,1,5,9,2,6,5,3,5,8,9
We'll choose arr[0] as pivot.
Now take two variables, say i and j.
j will point to the next < element than arr[0] from right.
i will point to the next >= element than arr[0] from left
so.. j will point to '2'
i will point to '4'.
SWAP
[3] 1,2,1,5,9,4,6,5,3,5,8,9
^ ^
i j
continue till j-i > 0.
so j will be at '1' when i moves to '1' j-i = 0 and loop breaks.
SWAP arr[j] with arr[0]
1,1,2 (3) 5,9,4,6,5,3,5,8,9
^
j
So, we see we have two sub-array partitions. 0 to j-1 and j+1 to n-1
Repeat and see what you get. :)
Best case for quick sort can be performed with a check that after a single pass if any swap is happening.
If not, then it is sorted, no need to go further.
Ex: 1,2,3,4,5,6
j starts from '6' and crosses i that is in '2'.
No swaps performed. So, sorted.
Quick Sort can be modified like this to give best case as O(n).
However in the traditional algorithm you have to go on partitioning to find it at O(nlog(n))
