Sorting in line

Computer Science Level 3

There are $x$ soldiers lined up in a row and sorted according to their heights. You want to reverse their order in the row in a minimum number of swaps. Any swap can be done by swapping of two soldiers next to each other.

-50 1 -49 50 49 -1

1 solution

Kunal Gupta
May 9, 2018

Swap every $i^{th}$ person with $(99 -i +1 )^{th}$ person.
As, $99$ is an odd number, so $50^{th}$ person will be in place. Hence we require $49$ swaps to sort them in reverse order

But the swaps are only allowed if the soldiers are standing next to each other

Agnishom Chattopadhyay - 3 years ago

Oh yes! Then I realise that, minimum swaps are $\frac{n(n-1)}{2}$ which will give $0$ as the answer

Kunal Gupta - 3 years ago

Sorting in line

1 solution

0 pending reports