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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
#1

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

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

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

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

Посчитать количество пар соседних элементов, которые имеют противоположные знаки - C++
посчитать количество пар соседних элементов, которые имеют противоположные знаки. размерность 200. диапазон -60 60. Заранее спасибо)))

Быстрая сортировка, подсчитать количество перестановок элементов массива - C++
Здравствуйте! Никак не могу подсчитать количество перестановок елементов массива в сортировке Хоара:( Сделал счетчик value в цикле while,...

Найти максимальное произведение двух соседних элементов массива - C++
В заданном одномерном массиве z1,z1...zn.Найти максимальное произведение двух соседних элементов.

Определение максимальной и минимальной суммы двух соседних элементов массива - C++
дан массив целых чисел написать программу для определения максимальной и минимальной суммы двух соседних элементов массива

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
zss
Модератор
Эксперт С++
6382 / 5947 / 1927
Регистрация: 18.12.2011
Сообщений: 15,264
Завершенные тесты: 1
17.06.2014, 09:53 #2
Если Вам количество перестановок нужно знать для оптимизации,
то не лучше ли измерять время сортировки?
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 10:14 #3
что значит посчитать количество перестановок соседних элементов??? каждая сортировка делает свое количество свопов соседних элементов!!! может в задача в том, чтобы посчитать количество инверсий в массиве?
0
Trwsdf
Заблокирован
17.06.2014, 10:19 #4
знать бы шо хочет автор уже половина решения
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
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
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 12:03 #6
как раз похоже на то, что надо найти количество инверсий в массиве.

что за сайт сказать можешь?
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
17.06.2014, 12:04  [ТС] #7
SlavaSSU, http://programmado.ru/59-sortirovka-sliyaniem-na-s.html вот.
0
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
17.06.2014, 12:13  [ТС] #8
SlavaSSU, Я думаю, что нет. Так как это сайт университета. Вот фото задачи.
0
Миниатюры
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?  
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
17.06.2014, 12:18  [ТС] #9
Помощь нужна срочно. Препод сказал, что желательно использовать сортировку слиянием.
0
Trwsdf
Заблокирован
17.06.2014, 13:03 #10
ты сначала определись что хотел, сортировку слиянием или то, что на фото. Сортировка слиянием на с++ выложена в гугле в википедии, так что вброс не удался.
0
SlavaSSU
215 / 160 / 45
Регистрация: 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
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
17.06.2014, 13:19 #12
Trwsdf, ему нужна такая сортировка, которая переставляя только соседние элементы даст минимум перестановок.
При этом переставлять сами элементы не надо, нужно только подсчитать перестановки.
1
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
17.06.2014, 13:20 #13
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?
Это из серии "Куда бы мне поехать, чтоб измерить пройденный путь?": хочешь - измеряй, не хочешь - не измеряй, с выбором пункта назначения это ни как не связано.
1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 674
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
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
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;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2014, 13:35
Привет! Вот еще темы с ответами:

Найти наибольшую по величине сумму двух соседних элементов массива - C++
Помогите с программой! Const N=10 ввод массивов с клавиатуры. Определить наибольшую по величине сумму двух соседних элементов массива.

Найти порядковые номера двух соседних элементов массива, сумма которых максимальна - C++
Найти порядковые номера двух соседних элементов массива, сумма которых максимальна. Если таких пар элементов несколько, то найти номера...

Перестановки: чтобы любые две соседние перестановки отличались только порядком двух соседних элементов - C++
Вводится число n &lt;= 8. Вывести все перестановки чисел 1,2..,n, так, чтобы две любые две соседние перестановки отличались только порядком...

Написать программу для определения максимальной и минимальной суммы двух соседних элементов массива - C++
Дан массив целых чисел Написать программу для определения максимальной и минимальной суммы двух соседних элементов массива


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.06.2014, 13:35
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru