210 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.
| 210 views

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

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