For 1st Number of Comparison is 6.

For 2nd Number Comparison is 10.

For 2nd Number Comparison is 10.

The Gateway to Computer Science Excellence

0 votes

What is the number of *Comparison * to sort below arrays using quick sort using first element as pivot ?

Please show steps .

A1=4,1,5,3,2

A2=1,2,3,4,5

+2

For 1st one

A1 = 4 1 5 3 2

After partition:-

2 1 3 4 5 Two subarrays are still to be sort those are A = 2 1 3 and B = 5 but till here num of comparisions are 4

Sorting A:-

A = 2 1 3

After partition:-

1 2 3 Two subarrays are still to be sort those are C = 1 and D = 3 but till here num of comp = 2

Sorting B, C and D will take 0 comparision because they are single elements.

Hence total number of Comparisions are 4 + 2 = 6

For 2nd one:-

A2 = 1 2 3 4 5

After partition only one array to be sort which is B = 2 3 4 5 till here num of comp = 4

sorting B = 2 3 4 5:-

After partition only one array to be sort which is C = 3 4 5 till here num of comp = 3

sorting C = 3 4 5:-

After partition only one array to be sort which is D = 4 5 till here num of comp = 2

sorting D = 4 5:-

After partition only one array to be sort which is E = 5 till here num of comp = 1

sorting E = 5 will take 0 comparisions because it is single element array so num of comp = 0

Total number of comparision is = 4 + 3 + 2 + 1 + 0 = 10.

A1 = 4 1 5 3 2

After partition:-

2 1 3 4 5 Two subarrays are still to be sort those are A = 2 1 3 and B = 5 but till here num of comparisions are 4

Sorting A:-

A = 2 1 3

After partition:-

1 2 3 Two subarrays are still to be sort those are C = 1 and D = 3 but till here num of comp = 2

Sorting B, C and D will take 0 comparision because they are single elements.

Hence total number of Comparisions are 4 + 2 = 6

For 2nd one:-

A2 = 1 2 3 4 5

After partition only one array to be sort which is B = 2 3 4 5 till here num of comp = 4

sorting B = 2 3 4 5:-

After partition only one array to be sort which is C = 3 4 5 till here num of comp = 3

sorting C = 3 4 5:-

After partition only one array to be sort which is D = 4 5 till here num of comp = 2

sorting D = 4 5:-

After partition only one array to be sort which is E = 5 till here num of comp = 1

sorting E = 5 will take 0 comparisions because it is single element array so num of comp = 0

Total number of comparision is = 4 + 3 + 2 + 1 + 0 = 10.

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

50,647 questions

56,492 answers

195,439 comments

100,711 users