The Gateway to Computer Science Excellence

+27 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?

- $n \log n$ steps
- $n^2$ steps
- $n$ steps
- $n^{1.5}$ steps
- The algorithm is not guaranteed to sort

+14 votes

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?

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

Odd numbered

processorsand even numberedprocessorsare activated alternate steps;

Question says it :)

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$

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})$

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.

+7 votes

+5 votes

+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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,394 answers

198,594 comments

105,445 users