The Gateway to Computer Science Excellence

+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))

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))

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,374 answers

198,512 comments

105,286 users