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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти сумму ряда http://www.cyberforum.ru/cpp-beginners/thread1210081.html
Здравствуйте уважаемые форумчане! Нуждаюсь в помощи. Имеется ряд http://firepic.org/images/2014-06/16/4mby1f0q9sec.png Необходимо найти его сумму. Visual C++, консольное приложение. Желательно...
C++ Алгоритм Фибоначчи Пользователь вводит любые два числа и количество операций, программа должна два числа сложить и результат записать в конец, после сложить два последних числа и так же записать в конец, и так... http://www.cyberforum.ru/cpp-beginners/thread1210048.html
Блок-схемы C++
Кто может нарисовать 7 блок-схем, не сложные по видимому, но надо поскорее кто сечет отпишите плиз
C++ Набор инструментов для инди с мультиплеером по ip
Подскажите какие библиотеки подключать для создания игр в стиле контры, марио, battle toads... Только с поддержкой качественной графики и возможностью игры с аппонентами через локальную сеть,...
C++ Сохранение результатов в текстовый документ http://www.cyberforum.ru/cpp-beginners/thread1210039.html
Добрый день. Нужна помощь, в данный код нужно добавить возможность сохранения результатов в текстовый документ. #include <iostream> using namespace std; int main() { double x, y, o; ...
C++ Библиотеки glut.lib и glut32.lib не могу найти Здравствуйте товарищи, помогите с очередной дилеммой. На днях начал изучать программирование, скачал Dav C++, но для дальнейших уроков нужны библиотеки - glut.h , glut32.blut , glut.bll , glut32.lib.... подробнее

Показать сообщение отдельно
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
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". В чем проблема?
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru