Матч 301, Сортировка вставками (InsertionSortCount)

Дивизион 2, Уровень 1

Рассмотрим алгоритм сортировки вставками. При вставке очередного элемента в упорядоченную последовательность часть элементов должна сдвигаться вправо. Например, рассмотрим сортировку массива {20,40,30,10}:

1. {20}. Число 20 ставится в ячейку с индексом 1. Сдвигов нет.

2. {20, 40}. Число 40 ставится в ячейку с индексом 1. Сдвигов нет.

3. {20, 30, 40}. Число 30 ставится в ячейку с индексом 1. Число 40 сдвигается на одну ячейку вправо.

4. {10, 20, 30, 40}. Число 10 ставится в ячейку с индексом 0. Числа 20, 30 и 40 сдвигаются вправо (три сдвига).

Таким образом, для сортировки вставками массива {20,40,30,10} следует совершить 4 сдвига. В задаче необходимо подсчитать общее количество сдвигов при сортировке вставками чисел заданного массива.

Класс: InsertionSortCount

Метод: int countMoves(vector<int> a)

Ограничения: массив a содержит от 1 до 50 элементов, -1000 £ a[i] £ 1000, все элементы массива a разные.

Вход. Массив чисел a. Все числа в массиве разные.

Выход. Количество сдвигов элементов при сортировке вставками.

Пример входа

a

{20,40,30,10}

{-1,1,0}

{-1000,0,1000}

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

4

1

0

РЕШЕНИЕ

сортировка

Пусть уже имеется отсортированная подпоследовательность {b₁, b₂, …, b_k}. При вставке очередного, a_k+1 - го числа, сдвигаются те и только те элементы b_i (1 £ i £ k), для которых a_k+1 < b_i. С другой стороны, элемент b_i (1 £ i £ k) будет сдвигаться тогда и только тогда, когда будет вставляться элемент a_k+1, для которого a_k+1 < b_i. В обоих случаях сдвигу подлежит такое количество элементов исходного массива, сколько существует пар (i, j), для которых i < j и a[i] > a[j]. То есть число сдвигов равно количеству инверсий в исходной последовательности.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class InsertionSortCount

{

public:

int countMoves(vector<int> a)

{

int i, j, res;

for(res = i = 0; i < a.size() - 1; i++)

for(j = i + 1; j < a.size(); j++)

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

return res;

}

};