1,697 views

2 Answers

Best answer
1 votes
1 votes
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))
selected by

Related questions

0 votes
0 votes
1 answer
1
dhruba asked Jun 5, 2023
411 views
Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?a. 1/n...
2 votes
2 votes
3 answers
2
LavTheRawkstar asked Apr 15, 2017
1,186 views
With quick sort The results after first partioning of the given array. A = (2,8,7,1,3,5,6,4,9).Analysis the time complexity of Quick sort in the best case.