880 views

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

A1=4,1,5,3,2

A2=1,2,3,4,5

| 880 views
0
For 1st Number of Comparison is 6.

For 2nd Number Comparison is 10.
0
for both?

explain step?
+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.
0
@shubhanshu,, At every step number of comparison will be size of current array minus one??
0
Yes.