Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Правила Карта форума Темы раздела Блоги Социальные группы Поиск Сообщения за день  
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
1

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

17.06.2014, 02:39. Показов 2204. Ответов 17
Метки нет (Все метки)
Всем привет. Я раньше создавал подобную тему, но решил создать новую. Вопрос следующий. Скажите, каким видом сортировки массива можно воспользоваться, чтобы посчитать количество перестановок двух соседних элементов?
Дело в том, что сортировка пузырьком - медленный способ. А в сортировке слиянием, как мне сказали, подсчитать количество перестановок проблематично. Заранее спасибо.

Добавлено через 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++;
Но я думаю, что так нельзя.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Сообщение: #6329623
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 17.06.2014, 02:39
Ответы с готовыми решениями:

Написать программу, реализующую сортировку одномерного массива методом обмена.(Найти количество перестановок элементов)
Написать программу, реализующую сортировку одномерного массива методом обмена.Найти количество...

Нужно вставить счетчик, чтобы посчитать количество сравнений и перестановок
#include &lt;iostream&gt; #include &lt;ctime&gt; using namespace std; int main() { int arr, a, b, i,...

Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов
Помогите пожалуйста в алгоритме быстрой сортировки посчитать количество перестановок и сравнений...

Посчитать сумму каждых 2-х соседних элементов массива.
Нужно зациклить создания массива состоявшейся из суммы двух соседних элементов до того момента...

17
Модератор
Эксперт С++
12630 / 10128 / 6097
Регистрация: 18.12.2011
Сообщений: 27,159
17.06.2014, 09:53 2
Если Вам количество перестановок нужно знать для оптимизации,
то не лучше ли измерять время сортировки?
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 10:14 3
что значит посчитать количество перестановок соседних элементов??? каждая сортировка делает свое количество свопов соседних элементов!!! может в задача в том, чтобы посчитать количество инверсий в массиве?
0
Заблокирован
17.06.2014, 10:19 4
знать бы шо хочет автор уже половина решения
0
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
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". В чем проблема?
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 12:03 6
как раз похоже на то, что надо найти количество инверсий в массиве.

что за сайт сказать можешь?
0
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
17.06.2014, 12:04  [ТС] 7
SlavaSSU, http://programmado.ru/59-sorti... -na-s.html вот.
0
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
17.06.2014, 12:13  [ТС] 8
SlavaSSU, Я думаю, что нет. Так как это сайт университета. Вот фото задачи.
Миниатюры
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?  
0
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
17.06.2014, 12:18  [ТС] 9
Помощь нужна срочно. Препод сказал, что желательно использовать сортировку слиянием.
0
Заблокирован
17.06.2014, 13:03 10
ты сначала определись что хотел, сортировку слиянием или то, что на фото. Сортировка слиянием на с++ выложена в гугле в википедии, так что вброс не удался.
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
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;
}
1
3980 / 3250 / 909
Регистрация: 25.03.2012
Сообщений: 12,084
Записей в блоге: 1
17.06.2014, 13:19 12
Trwsdf, ему нужна такая сортировка, которая переставляя только соседние элементы даст минимум перестановок.
При этом переставлять сами элементы не надо, нужно только подсчитать перестановки.
1
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
17.06.2014, 13:20 13
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?
Это из серии "Куда бы мне поехать, чтоб измерить пройденный путь?": хочешь - измеряй, не хочешь - не измеряй, с выбором пункта назначения это ни как не связано.
1
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
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;
 
}
Как мне в этом коде подсчитать количество инверсий при сортировке?
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 13:35 15
Лучший ответ Сообщение было отмечено Sh@dow777 как решение

Решение

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

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;
}
1
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
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;
 
}
подсчет инверсий проблематично сделать?
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 13:53 17
если просто сказать, то нет, не сложно!!!
у вас что надо просто сдать прогу, а объяснять как он работает не обязательно, по желанию!!??)))
1
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
17.06.2014, 13:57  [ТС] 18
SlavaSSU, Нет, объяснять не нужно. Я понял, как она работает. Еще раз большое спасибо.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 17.06.2014, 13:57
Помогаю со студенческими работами здесь

одномерный массив посчитать количество пар соседних элементов одного знака
19. Для одномерного массива посчитать количество пар соседних элементов одного знака

Посчитать количество пар соседних элементов, которые имеют противоположные знаки
посчитать количество пар соседних элементов, которые имеют противоположные знаки. размерность 200....

Массив: Найти количество элементов, значение которых больше суммы двух соседних элементов.
Дан массив из N элементов. Найти количество элементов, значение которых больше суммы двух соседних...

Количество перестановок и время затраченное на сортировку
Количество перестановок и время затраченное на сортировку.


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru