3,069 views
34 votes
34 votes

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?

  1. $n \log n$ steps
  2. $n^2$ steps
  3. $n$ steps
  4. $n^{1.5}$ steps
  5. The algorithm is not guaranteed to sort

4 Answers

Best answer
17 votes
17 votes

Answer: C.

selected by
7 votes
7 votes

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.

5 votes
5 votes
OPTION C is correct.
edited by
2 votes
2 votes
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
Answer:

Related questions

15 votes
15 votes
2 answers
3