Сортировка Слиянием

[MahovIV]

Мне нужно создать программу, в которой используется сортировка слиянием. Нужно пересчитать количество перестановок. Программа выглядит так.

#include <iostream>
#include <conio.h>

using namespace std;

#define maxn 173000

int a[maxn];

int n;
int pr = 0;

void merge(int l, int r) {
if (r == l)
return;
if (r - l == 1) { 
if (a[r] < a[l])
swap(a[r], a[l]);
return;
}
int m = (r + l) / 2;
merge(l, m);
merge(m + 1, r);
int buf[maxn];
int xl = l;
int xr = m + 1;
int cur = 0;
while (r - l + 1 != cur) {
if (xl > m) {
buf[cur++] = a[xr++];
pr++;
}
else if (xr > r) {
buf[cur++] = a[xl++];
pr++;
}
else if (a[xl] > a[xr]) {
buf[cur++] = a[xr++];
pr++;
}
else {
buf[cur++] = a[xl++];
pr++;
}

}
for (int i = 0; i < cur; i++)
a[i + l] = buf[i];
}

int main() {	
cin >> n;

for (int i = 0; i < n; i++)
cin >> a[i];

merge(0, n - 1);

for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << pr << "\n";

getch();
return 0;
}

Код
while (r - l + 1 != cur) {
if (xl > m) {
buf[cur++] = a[xr++];
pr++;
}
else if (xr > r) {
buf[cur++] = a[xl++];
pr++;
}
else if (a[xl] > a[xr]) {
buf[cur++] = a[xr++];
pr++;
}
else {
buf[cur++] = a[xl++];
pr++;
}
}
делает перестановку.
Я не понимаю, где нужно добавить счётчик pr++? При maxn = 500000 программа принудительно закрывается. Какой вариант сортировки лишён этого недостатка?

 

[Whatka]

ужасный стиль кода(это всего лишь моё мнение)

При maxn = 500000 программа принудительно закрывается. Какой вариант сортировки лишён этого недостатка?

int a[maxn];

при чём тут сортировка? это же размер массива
Или вы знаете способ сортировки последовательности чисел,зависящий от реализации после-ности на языке программирования?

и что такое перестановка?какое формальное значение вы определяете для данного слова?

поясняю мой вопрос:
пусть это кол-во чисел изменений полжений чисел относительно начального-
тогда вы прстой операцией инкремента в строке точно не сможете определить это,
надо учесть и просто изменение положения 2 чисел и изменения положения групп чисел(причём некоторые числа,входящие в группу могут не изменить своё начальное положение или вернуться на него) и т.д. я вообще сомневаюсь,что это реально сделать за хотя бы ту же трудоёмкость,что и саму сортировку

 

[MahovIV]

ужасный стиль кода(это всего лишь моё мнение)


при чём тут сортировка? это же размер массива
Или вы знаете способ сортировки последовательности чисел,зависящий от реализации после-ности на языке программирования?

и что такое перестановка?какое формальное значение вы определяете для данного слова?

поясняю мой вопрос:
пусть это кол-во чисел изменений полжений чисел относительно начального-
тогда вы прстой операцией инкремента в строке точно не сможете определить это,
надо учесть и просто изменение положения 2 чисел и изменения положения групп чисел(причём некоторые числа,входящие в группу могут не изменить своё начальное положение или вернуться на него) и т.д. я вообще сомневаюсь,что это реально сделать за хотя бы ту же трудоёмкость,что и саму сортировку

Вы можете мне помочь?

 

[Whatka]

Вы можете мне помочь?

Да,если вы четко сформлируете своё задание

 

[MahovIV]

Условие задачи:В этой задаче вам необходимо проанализировать некоторый алгоритм сортировки. Этот алгоритм сортирует последовательность из N различных целых чисел, переставляя по два соседних элемента последовательности до тех пор, пока она не будет упорядочена по возрастанию. Ваша задача состоит в том, чтобы посчитать, сколько таких перестановок двух соседних элементов необходимо сделать, чтобы отсортировать заданную последовательность.
Я узнал, что нужно использовать сортировку слиянием.

 

[rrrFer]

и что такое перестановка?какое формальное значение вы определяете для данного слова?

Имеется ввиду перестановка двух любых элементов массива. Если элемент переставился, а потом вернулся назад - это 2 перестановки )
Количество перестановок оценивают трудоемкость алгоритма, вот препод и хочет чтобы ТС посчитал это.

я вообще сомневаюсь,что это реально сделать за хотя бы ту же трудоёмкость,что и саму сортировку

вобще реально, но этоо не важно, задача ведь учебная )

Сначала надо написать программу, которая просто сортирует массив, а уже потом вкручивать подсчет перестановок (сортировку можно найти на википедии), непойму в чем проблема.

Но есть один момент:

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

Чето я не пойму, как сортировка слиянием связана с перестановкой соседних элементов. И я не понял какой метод сортировки вы пытались в своем коде запилить.

Про слияние тут прочитать можно: (хотя там реализация на Прологе и элементы в массивах вобще не переставляются)

Ссылка скрыта от гостей

Суть слияния в том, что массив делится пополам, каждый из подмассивов делится еще раз пополам и т.п. до тех пор, пока массивы не станут достаточно маленькими. К маленьким массивам могут применяться любые алгоритмы сортировки. А потом отсортированные массивы начинаются сливаться в один большой отсортированный массив - и эта операция занимает кучу времени (только при этом происходят перестановки любых, а не только соседних элементов).

Че вам посчитать то надо?

 

[MahovIV]

Нужно посчитать перестановки соседних элементов.

 

[rrrFer]

Нужно посчитать перестановки соседних элементов.

Нужно - посчитай. Если есть конкретный вопрос - задавай.