10327. Сортировка перестановками

В задаче требуется отсортировать массив чисел. При этом разрешается совершать лишь одну операцию: менять местами два соседних числа. Необходимо найти минимальное число таких перестановок, в результате которых массив чисел будет отсортирован по возрастанию.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество целых чисел n (n £ 1000), подлежащих сортировке. В следующей строке находятся сами n чисел.

Выход. Для каждого теста вывести согласно приведенному ниже формату минимальное число операций перестановки двух соседних элементов, в результате которых будет отсортирован массив по возрастанию.

Пример входа

3

1 2 3

3

2 3 1

Пример выхода

Minimum exchange operations : 0

Minimum exchange operations : 2

РЕШЕНИЕ

сортировка

Анализ алгоритма

Пусть a₁, a₂, …, a_n – некоторая последовательность чисел. Если i < j и a_i > a_j, то пара (a_i, a_j) называется инверсией. Минимальное количество перестановок соседних элементов, которое следует совершить для сортировки последовательности, равно числу инверсий в ней.

Пример

Для сортировки чисел со второго теста следует совершить две перестановки соседних элементов:

2 3 1 à 2 1 3 à 1 2 3

Реализация алгоритма

Читаем входную последовательность из n чисел в массив m.

while(scanf("%d",&n) == 1)

{

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

В переменную res заносим количество инверсий во входной последовательности и выводим результат.

res = 0;

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

if (m[i] > m[j]) res++;

printf("Minimum exchange operations : %d\n",res);

}