LPU MATERIALS

Question

Number of comparisons required to sort letters in ALGORITHM?

(A) 36 (B) 8
(C) 45 (D) 9

Answer 1

The answer would be $36$ .

Question asks for number of comparisons, it neither specifies maximum or minimum. Neither it specifies sorting technique nor it specifies whether we need to sort ascending or descending. In such case there are just so many answers.

For sorting such as Bubble Sort , Selection Sort we would take fixed $\frac {n\times(n-1)}{2} $ comparisons for both ascending or descending sequence, that gives answer $36$

Merge Sort would give least number of maximum comparisons for general cases ,and would be same irrespective of ascending or descending, and it would be at most $(n\left \lceil log_2(n) \right \rceil- 2^{\left \lceil log_2(n) \right \rceil} +1 )$.

For this question merge sort takes $21$ comparisons.

and then there is Insertion Sort which takes $d+(n-1)$ comparisons, where $d$ is number of inversions.

Two elements $a[i]$ and $a[j]$ form an inversion if $i < j$  and $a[i] > a[j]$ 

In word ALGORITHM there are $12$ inversions, hence for ascending  $ 12+8=20$ comparisons

and for descending $\frac {n\times(n-1)}{2} -12+8=24+8=32$ comparisons

Comments

which site did you use to make this flowchart?

---

Lucid $\leftarrow$ 

I haven't tried much so , if there is anything else which might be better do let me know.

---

https://app.diagrams.net/  I use this one.

---

Oh, nice👍

Answer 2

On using the merge sort technique, the number of comparisons required to sort n elements is n-1

In ALGORITHM we have 9 letters so we need 8 comparisons 

Comments

To merge two sorted array of size $I$ and $J$ the algorithm would do $I+J-1$ comparisons.

If we have total size $=n$, and we divide the array in to two halves,$\lfloor \frac n 2 \rfloor$ and $\lceil \frac n 2\rceil $.at the time of merging these array, (when both of them are exclusively sorted), we would need

$\lfloor \frac n 2 \rfloor+\lceil \frac n 2\rceil -1=n-1$ comparisons. But you forgot to count the comparisons it needs to sort those individual array.

If you need further intuition,

actually attempt the question. the array of ALGORITHM would look like following,

$[65,76,71,79,82,73,84,72,77]$