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

Сортировка слиянием. Количество инверсий - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
Rostislav1
0 / 0 / 0
Регистрация: 04.05.2013
Сообщений: 7
14.05.2013, 18:14     Сортировка слиянием. Количество инверсий #1
Нужно посчитать количество инверсий в последовательности. При больших значениях ~90 - 100 тысяч программа выдает непонятное отрицательно число. Где ошибка?
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
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
int tmp = 0;
vector<int> mas;
int merge(vector<int> &mas, int l, int m, int r)
{
    int per = 0;
    vector<int> buffer(r - l + 1);
    int pos1 = l;
    int pos2 = m+1;
    int posB = 0;
 
    while(pos1 <=m && pos2<=r)
    {
        if(mas[pos1] < mas[pos2])
            buffer[posB++] = mas[pos1++];
        else
        {
            buffer[posB++] = mas[pos2++];
            per += m - pos1 + 1;
        }
    }
 
    while (pos1 <=m)
        buffer[posB++] = mas[pos1++];
    while (pos2 <=r)
        buffer[posB++] = mas[pos2++];
    copy(buffer.begin(), buffer.end(), mas.begin()+l);
    return per;
 
}
int merge_sort(vector<int> & mas, int l, int r)
{
    int per = 0;
    if(l == r)
        return per;
    int m = (l + r)/2;
    per +=merge_sort(mas, l,m);
    per +=merge_sort(mas, m+1,r);
    per += merge(mas, l, m, r);
    return per;
}
void input()
{
    cin>>n;
    mas.resize(n);
        for (int j=0;j<n;j++)
            scanf("%d",&mas[j]);
      int per= merge_sort(mas,0,n-1);     
            tmp = per;
}
void output()
{
    printf("%d\n", tmp);
}
int main()
{
    input();
    output();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2013, 18:14     Сортировка слиянием. Количество инверсий
Посмотрите здесь:

C++ Сортировка слиянием
Определить количество инверсий в последовательности C++
шейкерная сортировка + сортировка слиянием C++
C++ [Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки
Сортировка слиянием C++
C++ Сортировка слиянием: подсчитать количество перестановок
C++ Определить количество инверсий в целочисленном массиве
Определить количество инверсий в массиве C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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