0 votes
450 views
A list of elements are given A - <3,1,4,1,5,9,2,6,5,3,5,8,9 >

Show Howw the "Pivot" and quick sort algorithm work.

finally show the Best Case analysis for quick sort .
| 450 views

## 2 Answers

+1 vote
Best answer
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))
by (351 points)
selected
0 votes
by Boss (42.5k points)

0 votes
1 answer
1
0 votes
1 answer
2
0 votes
1 answer
3