TIFR CSE 2013 | Part B | Question: 20

Question

Suppose $n$ processors are connected in a linear array as shown below. Each processor has a number. The processors need to exchange numbers so that the numbers eventually appear in ascending order (the processor $\rm P1$ should have the minimum value and the the processor $\rm Pn$ should have the maximum value).

The algorithm to be employed is the following. Odd numbered processors and even numbered processors are activated alternate steps; assume that in the first step all the even numbered processors are activated. When a processor is activated, the number it holds is compared with the number held by its right-hand neighbour (if one exists) and the smaller of the two numbers is retained by the activated processor and the bigger stored in its right hand neighbour.
How long does it take for the processors to sort the values?

• A. $n \log n$ steps
• B. $n^2$ steps
• C. $n$ steps
• D. $n^{1.5}$ steps
• E. The algorithm is not guaranteed to sort

Answer 1

Answer: C.

Comments

@Soumya29

why do u say that constant time is required to swap?the value of n is not fixed.

---

They are asking for steps here not time complexity. In each step even/odd processors are doing constant work i.e they are activated simulatenously and swapping is done.

---

Why can't it be seen as 2-way merge sort?

Answer 2

Exact N step take take worst case decresing oder . 1st elemnt come to its coreect place at n th step at the same time all elemnt goes to its coreect place.

Comments

Explain it with example.

---

Small example n=4

     4 3 2  1

Even :  3 4 1 2

Odd ;  3 1 4 2

even :   13 2 4

odd:     1 2 3 4

N steps are required

Answer 3

OPTION C is correct.

Comments

i gave step wise,

in the quesition-- "IN first step all the even numbered processors are activated" line is there.

---

okk that means , once they  have activated ... we can exchanged same time rt  ..

---

yes.like that only...

Answer 4

We can also think in this way:

The total number of inversions in any array = ((n)(n-1))/2

At every step: n/2 inversions are getting corrected.

So the total number of steps required will be = ((n)(n-1))/2) / (n/2) = n-1 steps

Example:

let the number of elements in the array be n = 8.

The total numbers of inversion possible = (8*7)/2 = 28

The number of inversions corrected 1 step = 4

The total number of steps needed to correct 28 inversions = 28/4 = 7, approximately equal to n

So the option C