ISI2011-PCB-CS-1b

Question

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.

Answer 1

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

b) n-1 swaps in all cases

Comments

But selection sort will not follow successively swapping pairs of adjacent elements.

Answer 2

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.

 

Comments

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