GATE CSE 1996 | Question: 2.15

Question

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot

1. $1, 2, 3, \dots n$
2. $n, n-1, n-2, \dots, 2, 1$

Let $C_1$ and $C_2$ be the number of comparisons made for the inputs (i) and (ii) respectively. Then, 

• A. $C_1 < C_2$
• B. $C_1 > C_2$
• C. $C_1 = C_2$
• D. we cannot say anything for arbitrary $n$

Comments

• Same number of comparisons: structure of recursion tree is identical

• Swap behavior differs, but question only asks about comparisons

---

no, if sorted in decreasing order then it is going to give n(n-1/2 because in swap we check which element is smaller

---

similar question https://gateoverflow.in/80366/gate-cse-1987-question-1-xviii

Answer 1

Correct Option: C
both are the worst cases of quick sort. (assuming pivot is either first or last element)

1. is sorted in ascending order.
2. is sorted in descending order.

Comments

explain anyone ... specifically abt the pivot element......

---

If you consider like a tree then the no of comparison at each levels depends upon 'n' and if the pivot element is last in case of an already sorted array. Then no of levels = n. Thus no of comparison = n*n.

In case of an unsorted array no of comparison considering logn levels= n*logn.

So shouldn't c1>c2? (Assuming the last element is choosen as the pivot always)

---

If the same algorithm is used for running both arrays and the algorithm chooses the last element as the pivot, then the comparisons will be C1<C2 and vice versa if the pivot chosen is the first element.

If the pivot chosen is the middle element, every time, then C1=C2.

Answer 2

1)ascending case==>Comparisons(C1)=(n-1)+(n-2)+(n-3)+.........................+2+1

                                                               =n(n-1)/2

                                                               =o(n^2)

                                             Swaps(S1)=1+1+1+............................................+1(upto n pass)

                                                               =n

                                                               =o(n)

2)Descending case==>Comparisons(C2)=(n-1)+(n-2)+(n-3)+....................................+1

                                                                 =n(n-1)/2

                                                                 =o(n^2)

                                               Swaps(S2)=(n)+(1)+(n-2)+(1)+(n-4)+...........(ascending and descending cases will come alternatively)                                           

                                                                 =3n^2/4

                                                                =o(n^2)

so C1=C2 and S1<S2

 

                                                                =

Comments

@Mk Utkarsh 

i am not getting why that "single" swap required if array is sorted in ascending order, as pivot is placed correctly ( say left end element as pivot ) and all right side elements are larger and lhs are smaller ( though nothing is in lhs ).. So where single swap is needed ?

are we swapping element with itself hence "1" swap ?

---

@talha hashim please explain how you are calculating swaps when input is in descending order?

---

This is what I think:

In ascending order :
                  No. of comparisons = (n-1)+(n-2)+......+1  = O(n^2)
                  No. of swappings = (n)+(n-1)+......+1  = O(n^2)     [here every element will be swapped with itself ]

In descending order :
                  No. of comparisons = (n-1)+(n-2)+......+1  = O(n^2)
                  No. of swappings = 1+1+1+......n times = O(n)     [here only pivot element will be swapped]

---

No.of swappings for ascending order will be O(n) because it is 1 + 1 + 1 + 1 + ...

Answer 3

I think answer is C1>C2 because in ascending input left do 1 comparison and than stops and than right do all comparison until left=right. But in descending input left keeps going until left=right and right won't do any comparison because according to algorithm right start moving only after left finds a key which is larger than pivot which is not in the case of descending input.

Comments

Thanks

Answer 4

From my POV - As both are the Worst Cases for QuickSort and Question ask for the No. of Comparisons and Both have the equal No. of Elements So, the Answer is (C) C1=C2

Please Correct me if I'm Wrong.....

Answer 5

Here is one solution.