У меня есть программа сортировки слиянием, где я считаю число инверсий. В функции main просто создается массив, в который считывается количество элементов массива и сами элементы из входного файла. А затем в выходной файл выводится число инверсий.
Я понимаю, как работает сортировка слиянием и что такое инверсии, но мне не понятно, как сама программа это делает:
1)В функции merge_sort_1
мы разбиваем наш массив на левую и правую часть, а затем левую и правую также делим пополам, пока не останутся массивы, в которых будет ровно два элемента, а затем мы все эти элементы передаем в функцию merge_sort_2
и в ней все эти массивы сливаются и сортируются? Если это так, то как именно работает merge_sort_1
?
Я пробовал сам на листочке расписать этот алгоритм подставив в первую функцию сам массив, левую и правую границы, но из этого ничего не получилось, я не увидел каким образом наш массив делится пополам. И когда мы пишем
merge_sort_1(array, left, middle);
merge_sort_1(array, middle, right)-
если, например исходный массив равен 4 3 2 1
, то после этих функций должно быть два массива [4 3]
и [2 1]
? Если это так, то куда записываются эти два массива, если здесь один массив array
, который мы передаем потом в merge_sort_2
?
Если мы работаем постоянно в одном массиве, просто благодаря middle
мы делим массив, то тоже не понятно, что в итоге должно получиться после этих функций. И что мы в конце концов передадим в функцию merge_sort_2
? Мы пишем - merge_sort_2(array, left, middle, right);
первое, что мы передаем - это array
, т.е. наш массив. А что именно в нем будет находиться, после выполнения тех двух функций, а также в каждом из параметров, который мы передаем в функцию merge_sort_2
, например, если у нас был массив 4 3 2 1
?
Эта функция должна разбить эти массивы на два 4 3
и 2 1
, но как эти два массива могут быть в одном array
? Если же в array
в это моменте будет 4 3 2 1
, то какой вообще смысл этой функции?
- Почему именно такая формула у числа инверсий? Я опять же пытался сам на листочке, подставив значения разобраться. Я подставил массив
4 3 2 1
, тут 6 инверсий. Но по такой формуле я насчитал только 4
3)Зачем мы вообще делаем условие while
? Я понимаю, что мы это делаем на тот случай, если левая сторона не дошла до середины или правая сторона не дошла до конца. Мне не понятно, почему такая ситуация может произойти.
#include <fstream>
#include <vector>
using namespace std;
long long amount;
void merge_sort_2(vector<int>& array, int left, int middle, int right)
{
vector<int> copy;
copy.resize(right - left);
int i, j;
i = 0;
j = 0;
while (((left + i) < middle) && ((middle + j) < right))
{
if (array[left + i] <= array[middle + j])
{
copy[i + j] = array[left + i];
i++;
}
else
{
copy[i + j] = array[middle + j];
amount += middle - (left + i);//формула для вычисления числа инверсий
j++;
}
}
while ((left + i) < middle)
{
copy[i + j] = array[left + i];
i++;
}
while ((middle + j) < right)
{
copy[i + j] = array[middle + j];
j++;
}
for (int k = 0; k < (i + j); k++)
{
array[left + k] = copy[k];
}
}
void merge_sort_1(vector<int>& array, int left, int right)
{
if ((left + 1) >= right)
{
return;
}
int middle;
middle = (left + right) / 2;
merge_sort_1(array, left, middle);
merge_sort_1(array, middle, right);
merge_sort_2(array, left, middle, right);
}
int main()
{
ifstream input("inversions.in");
ofstream output("inversions.out");
int n;
input >> n;
vector<int> array;
array.resize(n);
for (int i = 0; i < n; i++)
{
input >> array[i];
}
merge_sort_1(array, 0, n);
output << amount;
return 0;
}