995 views

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
| 995 views

by Boss (10.9k points)
selected
+3
Very good explanation. But take some small value of N.
0
Even numbered processors like P1, P3, P5,........ are activated or even numbers contained within processors P1, P2, P3,..... are activated?

Like say P1 = 4, P2 = 8, P3 = 1, P4 = 7, P5 = 6, P6 = 9, P7 = 5. Initially P2, P4, P6 are activated? Or processors containing even nos (P1 = 4, P2 = 8, P5 = 6) are activated?
0

@rfzahid

Odd numbered processors and even numbered processors are activated alternate steps;

Question says it :)

0
Number of steps will be n , but time complexity will be n^2 right?
0
Hello VS

Question said that even numbered processors are activated first and the will be compared with right hand side neighbor. You compared them with left hand neighbor although yet answer would be $n$.

o/p after first step would be

$8$   $6$   $7$   $4$   $5$  $2$  $3$  $1$
+1
Hello sourav basu

Yes! in each step there are almost $\frac{n}{2}$ comparisons and total steps are $n$ so time complexity is $n*\frac{n}{2}$=$O(n^{2})$
+10

According to question :-

1) "Each processor has a number" :- It means each processor has a value.

2) "The processors need to exchange numbers so that the numbers eventually appear in ascending order (the processor $P_{1}$ should have the minimum value and the the processor $P{n}$ should have the maximum value)." :- means relative position of processors is fixed. We are only exchanging the values of the processors so that all the values will be in ascending order(it implies that values are distinct due to the word 'ascending')

Now , given algorithm works like this on the  example given by VS :-

(Here ,  blue color entries represent the active state of the processors at each step.) Initially we have  :-

Step 1 :-

 $8$ $7$ $6$ $5$ $4$ $3$ $2$ $1$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Step 2 :-

 $8$ $6$ $7$ $4$ $5$ $2$ $3$ $1$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Step 3 :-

 $6$ $8$ $4$ $7$ $2$ $5$ $1$ $3$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Step 4 :-

 $6$ $4$ $8$ $2$ $7$ $1$ $5$ $3$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Step 5 :-

 $4$ $6$ $2$ $8$ $1$ $7$ $3$ $5$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Step 6 :-

 $4$ $2$ $6$ $1$ $8$ $3$ $7$ $5$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Step 7 :-

 $2$ $4$ $1$ $6$ $3$ $8$ $5$ $7$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Step 8 :-

 $2$ $1$ $4$ $3$ $6$ $5$ $8$ $7$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Final Sorted List :-

 $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $P_{1}$ $P_{2}$ $P_{3}$ $P_{4}$ $P_{5}$ $P_{6}$ $P_{7}$ $P_{8}$

Here , After $8$ steps ,We have sorted $8$ elements in ascending order. So, Answer :- (C)

+5
At first look, it appears that $\color{RED}{each \ step}$ will take $O(n)$ time and total $n$ steps will be required in worst case so $n*n=O(n^2)$ but $twist$ here is that at any step $\color{blue}A{ll}$ the even numbered (or odd numbered) processors are working(Comparing it's value with its right neighbour and swapping values if required) $\color{RED}{simultaneously}$. So at each step, a constant amount of time $(O(1))$ is required. so T.C will be $n*O(1) = \color{RED}{O(n)}$ only.
+1

@ankitgupta.1729

yes , u r right.

I thought, it will be like bubble sort. But it is not like that too. We have to completely run the array manually. right?

@VS

ur pass 2 not correct I think

+1

@srestha yes, right.

0

@Soumya29

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

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.

by Veteran (63k points)
0
Explain it with example.
+1
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
OPTION C is correct.
by Junior (883 points)
edited
0
in 6 4 5 7 ,you exchanged both even and odd ??
0
First even no processors are activated then next odd no processors are activated.

when they are active they cmp with right neighbour if any exist.
0
same time ,both will not be exchanged ....but you did 6 4 5 7 ... thats why i am asking
0

i gave step wise,

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

0
okk that means , once they  have activated ... we can exchanged same time rt  ..
0
yes.like that only...
+1 vote
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
by (177 points)