Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 02:39     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #1
Всем привет. Я раньше создавал подобную тему, но решил создать новую. Вопрос следующий. Скажите, каким видом сортировки массива можно воспользоваться, чтобы посчитать количество перестановок двух соседних элементов?
Дело в том, что сортировка пузырьком - медленный способ. А в сортировке слиянием, как мне сказали, подсчитать количество перестановок проблематично. Заранее спасибо.

Добавлено через 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++;
Но я думаю, что так нельзя.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2014, 02:39     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?
Посмотрите здесь:

посчитать количество пар соседних элементов, которые имеют противоположные знаки C++
C++ Выполнить сортировку массива по убыванию и проконтролировать ее результат. Произвести подсчет перестановок при сортировке
Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов C++
Найти порядковые номера двух соседних элементов массива, сумма которых максимальна C++
C++ Определение максимальной и минимальной суммы двух соседних элементов массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,154
Завершенные тесты: 1
17.06.2014, 09:53     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #2
Если Вам количество перестановок нужно знать для оптимизации,
то не лучше ли измерять время сортировки?
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
17.06.2014, 10:14     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #3
что значит посчитать количество перестановок соседних элементов??? каждая сортировка делает свое количество свопов соседних элементов!!! может в задача в том, чтобы посчитать количество инверсий в массиве?
Trwsdf
Заблокирован
17.06.2014, 10:19     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #4
знать бы шо хочет автор уже половина решения
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 11:48  [ТС]     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #5
Вот задание:

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

Первая строка входных данных содержит единственное натуральное число 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
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
17.06.2014, 12:03     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #6
как раз похоже на то, что надо найти количество инверсий в массиве.

что за сайт сказать можешь?
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 12:04  [ТС]     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #7
SlavaSSU, http://programmado.ru/59-sortirovka-sliyaniem-na-s.html вот.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 12:13  [ТС]     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #8
SlavaSSU, Я думаю, что нет. Так как это сайт университета. Вот фото задачи.
Миниатюры
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?  
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 12:18  [ТС]     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #9
Помощь нужна срочно. Препод сказал, что желательно использовать сортировку слиянием.
Trwsdf
Заблокирован
17.06.2014, 13:03     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #10
ты сначала определись что хотел, сортировку слиянием или то, что на фото. Сортировка слиянием на с++ выложена в гугле в википедии, так что вброс не удался.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
17.06.2014, 13:14     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #11
вот попробуй пошли вот это!
я там ее еще дебагал поэтому дофига комментов!
я не уверен что правильно, но просто интересно проверить!


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
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
17.06.2014, 13:19     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #12
Trwsdf, ему нужна такая сортировка, которая переставляя только соседние элементы даст минимум перестановок.
При этом переставлять сами элементы не надо, нужно только подсчитать перестановки.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
17.06.2014, 13:20     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #13
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?
Это из серии "Куда бы мне поехать, чтоб измерить пройденный путь?": хочешь - измеряй, не хочешь - не измеряй, с выбором пункта назначения это ни как не связано.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 13:27  [ТС]     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #14
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
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
17.06.2014, 13:35     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #15
Сообщение было отмечено автором темы, экспертом или модератором как ответ
все вот теперь без лишнего)

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
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 13:47  [ТС]     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #16
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
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
17.06.2014, 13:53     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #17
если просто сказать, то нет, не сложно!!!
у вас что надо просто сдать прогу, а объяснять как он работает не обязательно, по желанию!!??)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2014, 13:57     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?
Еще ссылки по теме:

Написать программу для определения максимальной и минимальной суммы двух соседних элементов массива C++
C++ Найти наибольшую по величине сумму двух соседних элементов массива
Найти максимальное произведение двух соседних элементов массива C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
17.06.2014, 13:57  [ТС]     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? #18
SlavaSSU, Нет, объяснять не нужно. Я понял, как она работает. Еще раз большое спасибо.
Yandex
Объявления
17.06.2014, 13:57     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?
Ответ Создать тему
Опции темы

Текущее время: 15:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru