Матч 151, Сортировка слиянием (MergeSort)

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

Рассмотрим сортировку методом слияния согласно следующему алгоритму:

Сортировка_Слиянием (массив а)

1. Если размер массива а £ 1, то вернуть а;

2. Разбить массив а на две части b и c:

2.1. Если массив а содержит 2*k чисел, то b содержит первые k чисел, c – последние k чисел;

2.2. Если массив а содержит 2*k + 1 число, то b содержит первые k чисел, c – последние k + 1 число;

3. sb = Сортировка_Слиянием (массив b);

4. sc = Сортировка_Слиянием (массив c);

5. return Слить(sb, sc);

Слить (массив b, массив c)

1. Создать пустой массив a;

2. Пока оба массива b и c не пустые, сравниваем первые элементы массивов b и c:

2.1. Если first(b) < first(c), то удалим первый элемент из b и добавим его в конец массива a;

2.2. Если first(b) > first(c), то удалим первый элемент из c и добавим его в конец массива a;

2.3. Если first(b) = first(c), то удалим первые элементы из b и из c и добавим их в конец массива a;

3. Если массив b или c пустой, добавим весь непустой массив в конец массива a;

4. return a;

Класс: MergeSort

Метод: int howManyComparisons(vector<int> numbers)

Ограничения: numbers содержит от 0 до 50 элементов, -2³¹ £ numbers[i] £ 2³¹.

Вход. Массив чисел numbers.

Выход. Количество сравнений, необходимое совершить описанному выше алгоритму сортировки слиянием.

Пример входа

Numbers

{1, 2, 3, 4}

{2, 3, 2}

{-17}

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

4

2

0

РЕШЕНИЕ

сортировка

Реализуем описанную сортировку слиянием и подсчитаем количество сравнений в переменной comps.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

class MergeSort

{

public:

int howManyComparisons(vector<int> a)

{

return mergeSort(a);

}

int mergeSort(vector<int> &a)

{

if (a.size() <= 1) return 0;

int k = a.size() / 2;

vector<int> b = vector<int>(a.begin(), a.begin() + k);

vector<int> c = vector<int>(a.begin() + k, a.end());

int cb = mergeSort(b);

int cc = mergeSort(c);

return cb + cc + merge(a, b, c);

}

int merge(vector<int> &a, vector<int> &b, vector<int> &c)

{

unsigned ai = 0, bi = 0, ci = 0, comps = 0;

while (bi != b.size() && ci != c.size() && ++comps)

if (b[bi] == c[ci])

{

a[ai++] = b[bi++];

a[ai++] = c[ci++];

}

else

if (b[bi] < c[ci]) a[ai++] = b[bi++];

else a[ai++] = c[ci++];

while (bi != b.size()) a[ai++] = b[bi++];

while (ci != c.size()) a[ai++] = c[ci++];

return comps;

}

};