Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?

@Sh@dow777 · Регистрация: 10.12.2013

Студворк — интернет-сервис помощи студентам

Всем привет. Я раньше создавал подобную тему, но решил создать новую. Вопрос следующий. Скажите, каким видом сортировки массива можно воспользоваться, чтобы посчитать количество перестановок двух соседних элементов?
Дело в том, что сортировка пузырьком - медленный способ. А в сортировке слиянием, как мне сказали, подсчитать количество перестановок проблематично. Заранее спасибо.

Добавлено через 1 час 9 минут
Вот, допустим, я написал такой код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <conio.h>
using namespace std;
 
int a[500000];
 
int main()
{
    int n;
    int s = 0;
 
    cin >> n;
 
    for(int i = 0;i < n;i++)
        cin >> a[i];
 
    sort(a,a+n);
 
    getch();
 
    return 0;
}

Можно ли в этом случае каким то образом подсчитать количество перестановок двух соседних элементов?
Я не знаю.... может что то типа

C++
1
2
while(sort(a,a+n))
s++;

Но я думаю, что так нельзя.

@zss · 17.06.2014, 09:53

Если Вам количество перестановок нужно знать для оптимизации,
то не лучше ли измерять время сортировки?

@SlavaSSU · 17.06.2014, 10:14

что значит посчитать количество перестановок соседних элементов??? каждая сортировка делает свое количество свопов соседних элементов!!! может в задача в том, чтобы посчитать количество инверсий в массиве?

@Trwsdf · 17.06.2014, 10:19

знать бы шо хочет автор уже половина решения

@Sh@dow777 · 17.06.2014, 11:48 **[ТС]**

Вот задание:

Входные данные

Первая строка входных данных содержит единственное натуральное число 1 ≤ N < 500000 - длину сортируемой последовательности. Каждая из последующих N строк содержит целое число 0 ≤ a[i] ≤ 999999999, i-ый элемент последовательности. Все элементы последовательности различны.

Выходные данные

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

Сортировку пузырьком пробовал. Она медленная. Пишет "Превышено максимальное время работы". Нашел в интернете реализацию сортировки слиянием.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <conio.h>
using namespace std;
 
int a[500000];
 
int n, s;
 
void merge(int l, int r) {
    s = 0;
    if (r == l)
        return;
    if (r - l == 1) { 
        if (a[r] < a[l]){
            swap(a[r], a[l]);
            s++;
        }
        return;
    }
    int m = (r + l) / 2;
    merge(l, m);
    merge(m + 1, r);
    int buf[500000];
    int xl = l;
    int xr = m + 1;
    int cur = 0;
    while (r - l + 1 != cur) {
        if (xl > m)
            buf[cur++] = a[xr++];
        else if (xr > r)
            buf[cur++] = a[xl++];
        else if (a[xl] > a[xr])
            buf[cur++] = a[xr++];
        else buf[cur++] = a[xl++];
 
    }
    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);
 
    cout << s;
 
    getch();
    return 0;
}

Переделал, как мне нужно, но мне выводит ошибку "Stack Overflow". В чем проблема?

@SlavaSSU · 17.06.2014, 12:03

как раз похоже на то, что надо найти количество инверсий в массиве.

что за сайт сказать можешь?

@Sh@dow777 · 17.06.2014, 12:04 **[ТС]**

SlavaSSU, http://programmado.ru/59-sorti... -na-s.html вот.

@Sh@dow777 · 17.06.2014, 12:13 **[ТС]**

SlavaSSU, Я думаю, что нет. Так как это сайт университета. Вот фото задачи.

@Sh@dow777 · 17.06.2014, 12:18 **[ТС]**

Помощь нужна срочно. Препод сказал, что желательно использовать сортировку слиянием.

@Trwsdf · 17.06.2014, 13:03

ты сначала определись что хотел, сортировку слиянием или то, что на фото. Сортировка слиянием на с++ выложена в гугле в википедии, так что вброс не удался.

@SlavaSSU · 17.06.2014, 13:14

вот попробуй пошли вот это!
я там ее еще дебагал поэтому дофига комментов!
я не уверен что правильно, но просто интересно проверить!

UPD::
да это верно! я на другом сайте послал - полное решение!))

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
 
using namespace std;
 
const int dxh[] = {-2, -2, 2, 2, -1, -1, 1, 1};
const int dyh[] = {-1, 1, -1, 1, -2, 2, -2, 2};
 
long long int inv = 0;
int a[555555], b[555555];
int n;
 
void merge(int l, int r)
{
    //cout << "ranges == " << l << ' ' << r << endl;
    int sz = r - l + 1;
    if(sz == 1)
        return;
    if(sz == 2)
    {
        if(a[l] > a[r])
        {
            int t = a[l];
            a[l] = a[r];
            a[r] = t;
            inv++;
        }
 
        return;
    }
 
    int mid = sz / 2;
    
    //vector<int> b, c;
 
    merge(l, l + mid - 1);
    merge(l + mid, r);
 
    //for(int i = mid; i < a.size(); i++)
        //c.push_back(a[i]);
 
    //vector<int> a1 = merge(b);
    //vector<int> a2 = merge(c);
 
    //int n = l + mid - 1 - l + 1;
    //int m = r - (l + mid) + 1;
 
    //vector<int> s;
 
    /*cout << "first vector == " << endl;
    for(int i = 0; i < n; i++)
        cout << a1[i] << ' ';
    cout << endl;
 
    cout << "second vector == " << endl;
    for(int i = 0; i < m; i++)
        cout << a2[i] << ' ';
    cout << endl;*/
 
    //int sz1 = (n - 1) - l + 1;
    int n = l + mid;
    int m = r + 1;
    /*int sz1 = (n - 1) - l + 1;
 
    cout << "befor sliv == " << endl;
    for(int i = l; i < n; i++)
        cout << a[i] << ' ';
    cout << endl;
    for(int i = l + mid; i < m; i++)
        cout << a[i] << ' ';
    cout << endl;*/
    int i = l, j = l + mid;
    //cout << "segments == " << i << ' ' << n - 1 << ' ' << j << ' ' << m - 1 << endl;
 
    int id = 0;
    long long cur = 0;
 
    while(i < n || j < m)
    {
        //cout << i << ' ' << j << endl;
        if(i < n)
        {
            if(j >= m || a[i] <= a[j])
            {
                b[id] = a[i];
                id++;
                //s.push_back(a[i]);
                i++;
            }
            else
            {
                b[id] = a[j];
                id++;
                //s.push_back(a[j]);
                j++;
                inv += (n - 1) - i + 1;
                cur += (n - 1) - i + 1;
                
            }
        }
        else
        {
            b[id] = a[j];
            id++;
            //s.push_back(a[j]);
            j++;
        }
    }
 
    int idx = 0;
    for(int i = l; i <= r; i++)
        a[i] = b[idx], idx++;
 
    /*cout << "after sliv == " << endl;
    for(int i = l; i <= r; i++)
        cout << a[i] << ' ';
    cout << endl;
    cout << "cur == " << cur << endl;*/
 
    //return s;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int val = 1000000;
    for(int i = 0; i < n; i++)
    {
        int ch;
        scanf("%d", &ch);
        //ch = val;
        val--;
        a[i] = ch;
    }
 
    /*cout << "begin" << endl;
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    cout << endl;*/
    //vector<int> res = merge(mas);
    merge(0, n - 1);
 
    /*cout << "res == " << endl;
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");*/
    printf("%lld\n", inv);
    return 0;
}

@Kuzia domovenok · 17.06.2014, 13:19

Trwsdf, ему нужна такая сортировка, которая переставляя только соседние элементы даст минимум перестановок.
При этом переставлять сами элементы не надо, нужно только подсчитать перестановки.

@taras atavin · 17.06.2014, 13:20

Сообщение от Sh@dow777

Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?

Это из серии "Куда бы мне поехать, чтоб измерить пройденный путь?": хочешь - измеряй, не хочешь - не измеряй, с выбором пункта назначения это ни как не связано.

@Sh@dow777 · 17.06.2014, 13:27 **[ТС]**

Trwsdf, Вот сортировка слиянием.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;
 
int A[500000], n, i;
 
void Merge(int *A, int first, int last)
{
int middle, start, final, j;
int *mas=new int[100];
middle=(first+last)/2;
start=first; 
final=middle+1;
for(j=first; j<=last; j++)
if ((start<=middle) && ((final>last) || (A[start]<A[final])))
{
mas[j]=A[start];
start++;
}
else
{
mas[j]=A[final];
final++;
}
for (j=first; j<=last; j++) A[j]=mas[j];
delete[]mas;
}
void MergeSort(int *A, int first, int last)
{
if (first<last)
{
MergeSort(A, first, (first+last)/2); 
MergeSort(A, (first+last)/2+1, last);
Merge(A, first, last);
}
}
int main()
{
 
cin>>n;
 
for (i=1; i<=n; i++)
{ 
    cin>>A[i];
}
MergeSort(A, 1, n);
 
for (i=1; i<=n; i++)
    cout<<A[i]<<" ";
 
return 0;
 
}

Как мне в этом коде подсчитать количество инверсий при сортировке?

@SlavaSSU · 17.06.2014, 13:35

все вот теперь без лишнего)

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
 
using namespace std;
 
long long int inv = 0;
int a[555555], b[555555];
int n;
 
void merge(int l, int r)
{
    int sz = r - l + 1;
    if(sz == 1)
    {
        return;
    }
    if(sz == 2)
    {
        if(a[l] > a[r])
        {
            int t = a[l];
            a[l] = a[r];
            a[r] = t;
            inv++;
        }
 
        return;
    }
 
    int mid = sz / 2;
 
    merge(l, l + mid - 1);
    merge(l + mid, r);
 
    int n = l + mid;
    int m = r + 1;
    int i = l, j = l + mid;
 
    int id = 0;
 
    while(i < n || j < m)
    {
        if(i < n)
        {
            if(j >= m || a[i] <= a[j])
            {
                b[id] = a[i];
                id++;
                i++;
            }
            else
            {
                b[id] = a[j];
                id++;
                j++;
                inv += (n - 1) - i + 1;         
            }
        }
        else
        {
            b[id] = a[j];
            id++;
            j++;
        }
    }
 
    int idx = 0;
    for(int i = l; i <= r; i++)
        a[i] = b[idx], idx++;
}
 
int main()
{
    scanf("%d", &n);
 
    for(int i = 0; i < n; i++)
    {
        int ch;
        scanf("%d", &ch);
        a[i] = ch;
    }
 
    merge(0, n - 1);
 
    printf("%lld\n", inv);
    return 0;
}

@Sh@dow777 · 17.06.2014, 13:47 **[ТС]**

SlavaSSU, Спасибо вам. Приняло решение. Можно еще вопрос? Скажите, я так понял, что в этом коде

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;
 
int A[500000], n, i;
 
void Merge(int *A, int first, int last)
{
int middle, start, final, j;
int *mas=new int[100];
middle=(first+last)/2;
start=first; 
final=middle+1;
for(j=first; j<=last; j++)
if ((start<=middle) && ((final>last) || (A[start]<A[final])))
{
mas[j]=A[start];
start++;
}
else
{
mas[j]=A[final];
final++;
}
for (j=first; j<=last; j++) A[j]=mas[j];
delete[]mas;
}
void MergeSort(int *A, int first, int last)
{
if (first<last)
{
MergeSort(A, first, (first+last)/2); 
MergeSort(A, (first+last)/2+1, last);
Merge(A, first, last);
}
}
int main()
{
 
cin>>n;
 
for (i=1; i<=n; i++)
{ 
    cin>>A[i];
}
MergeSort(A, 1, n);
 
for (i=1; i<=n; i++)
    cout<<A[i]<<" ";
 
return 0;
 
}

подсчет инверсий проблематично сделать?

@SlavaSSU · 17.06.2014, 13:53

если просто сказать, то нет, не сложно!!!
у вас что надо просто сдать прогу, а объяснять как он работает не обязательно, по желанию!!??)))

@Sh@dow777 · 17.06.2014, 13:57 **[ТС]**

SlavaSSU, Нет, объяснять не нужно. Я понял, как она работает. Еще раз большое спасибо.

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@zss Модератор 13773 / 10966 / 6491 Регистрация: 18.12.2011 Сообщений: 29,244
	17.06.2014, 09:53
	Если Вам количество перестановок нужно знать для оптимизации, то не лучше ли измерять время сортировки? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	17.06.2014, 10:14
	что значит посчитать количество перестановок соседних элементов??? каждая сортировка делает свое количество свопов соседних элементов!!! может в задача в том, чтобы посчитать количество инверсий в массиве? 0

@Trwsdf Заблокирован
	17.06.2014, 10:19
	знать бы шо хочет автор уже половина решения 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	17.06.2014, 12:03
	как раз похоже на то, что надо найти количество инверсий в массиве. что за сайт сказать можешь? 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	17.06.2014, 12:04 [ТС]
	SlavaSSU, http://programmado.ru/59-sorti... -na-s.html вот. 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	17.06.2014, 12:13 [ТС]
	SlavaSSU, Я думаю, что нет. Так как это сайт университета. Вот фото задачи. Миниатюры 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	17.06.2014, 12:18 [ТС]
	Помощь нужна срочно. Препод сказал, что желательно использовать сортировку слиянием. 0

@Trwsdf Заблокирован
	17.06.2014, 13:03
	ты сначала определись что хотел, сортировку слиянием или то, что на фото. Сортировка слиянием на с++ выложена в гугле в википедии, так что вброс не удался. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	17.06.2014, 13:19
	Trwsdf, ему нужна такая сортировка, которая переставляя только соседние элементы даст минимум перестановок. При этом переставлять сами элементы не надо, нужно только подсчитать перестановки. 1

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	17.06.2014, 13:53
	если просто сказать, то нет, не сложно!!! у вас что надо просто сдать прогу, а объяснять как он работает не обязательно, по желанию!!??))) 1

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	17.06.2014, 13:57 [ТС]
	SlavaSSU, Нет, объяснять не нужно. Я понял, как она работает. Еще раз большое спасибо. 0

Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?

Решение