The Gateway to Computer Science Excellence
+3 votes
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.
in Algorithms by Veteran (105k points) | 210 views

1 Answer

0 votes
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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,210 comments
104,902 users