# ISI2011-PCB-CS-1b

326 views

There are $n$ students of a class standing in a line. The students have to arrange themselves in ascending order on the basis of their roll numbers. This rearrangement of the line must be accomplished only by successively swapping pairs of adjacent students.

1. Design an algorithm for this purpose that minimizes the number of swaps required.
2. Derive an expression for the number of swaps needed by your algorithm in the worst case.

1 vote
a) Selection sort will be the answer. It uses minimum swaps.

b) n-1 swaps in all cases
0
But selection sort will not follow successively swapping pairs of adjacent elements.

Since rearrangement is only allowed by swapping pairs of adjacent elements/students we have to use Merge sort and not Selection sort. no of swaps required will be $log(n!)$ or $nlog n$. Though in theory in Merge sort we don’t need swaps because merge procedure is not implemented in that way but practically if we think inline/idea of the given question the merging the students to form them in sorted increasing order of their roll numbers is similar to swapping them.

The worst case occurs when the whole sequence is inverted. For example, Let’s assume student roll numbers are initially arranged in this manner -

8, 7, 6, 5, 4, 3, 2, 1

then we can treat this as divide step and start merging adjacent students by comparing and swapping(if required) then successively we will compare and swap (if required) the adjacent student pairs, then the adjacent student quadruples, etc..

The number of swaps required in the worst case would be n – 1.

1
even in merge sort,there can be comparisons between pairs which are not adjacent.i think only bubble sort uses comparison between adjacent pairs.

## Related questions

1
333 views
You are given $k$ sorted lists, each containing $m$ integers in ascending order. Assume that (i) the lists are stored as singly-linked lists with one integer in each node, and (ii) the head pointers of these lists are stored in an array. Write an ... if you were permitted to use only constant additional storage? Analyse the time complexity of your algorithm for each of the above two cases.
Solve the following recurrence ($n$ is a natural number): $T(n) = \begin{cases} 7T(n\div3)+n^2 & ;n>2 \\ 1 & ;n \leq 2. \end{cases}$
For the function given by the Karnaugh map shown below, you can change at most one $1$ or one $0$ entry to a DON'T CARE. Determine what single change of this kind produces the simplest two-level AND-OR realization. Assume both uncomplemented and complemented inputs are available.
Assume a machine has $4$ registers (one of which is the accumulator $A$) and the following instruction set. $\text{LOAD}$ and $\text{STORE}$ ... offset. Design an instruction encoding scheme that allows each of the above instructions (along with operands) to be encoded in $8$ bits.