Сортировка Слиянием

Тема в разделе "C/C++/C#", создана пользователем MahovIV, 13 сен 2013.

  1. MahovIV

    MahovIV New Member

    Регистрация:
    6 июл 2013
    Сообщения:
    2
    Симпатии:
    0
    Мне нужно создать программу, в которой используется сортировка слиянием. Нужно пересчитать количество перестановок. Программа выглядит так.
    Код (Text):
    #include <iostream>
    #include <conio.h>

    using namespace std;

    #define maxn 173000

    int a[maxn];

    int n;
    int pr = 0;

    void merge(int l, int r) {
    if (r == l)
    return;
    if (r - l == 1) {
    if (a[r] < a[l])
    swap(a[r], a[l]);
    return;
    }
    int m = (r + l) / 2;
    merge(l, m);
    merge(m + 1, r);
    int buf[maxn];
    int xl = l;
    int xr = m + 1;
    int cur = 0;
    while (r - l + 1 != cur) {
    if (xl > m) {
    buf[cur++] = a[xr++];
    pr++;
    }
    else if (xr > r) {
    buf[cur++] = a[xl++];
    pr++;
    }
    else if (a[xl] > a[xr]) {
    buf[cur++] = a[xr++];
    pr++;
    }
    else {
    buf[cur++] = a[xl++];
    pr++;
    }

    }
    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);

    for (int i = 0; i < n; i++)
    cout << a[i] << " ";
    cout << pr << "\n";

    getch();
    return 0;
    }
    Код
    while (r - l + 1 != cur) {
    if (xl > m) {
    buf[cur++] = a[xr++];
    pr++;
    }
    else if (xr > r) {
    buf[cur++] = a[xl++];
    pr++;
    }
    else if (a[xl] > a[xr]) {
    buf[cur++] = a[xr++];
    pr++;
    }
    else {
    buf[cur++] = a[xl++];
    pr++;
    }
    }
    делает перестановку.
    Я не понимаю, где нужно добавить счётчик pr++? При maxn = 500000 программа принудительно закрывается. Какой вариант сортировки лишён этого недостатка?
     
  2. Whatka

    Whatka Well-Known Member

    Регистрация:
    9 окт 2011
    Сообщения:
    433
    Симпатии:
    4
    ужасный стиль кода(это всего лишь моё мнение)
    при чём тут сортировка? это же размер массива
    Или вы знаете способ сортировки последовательности чисел,зависящий от реализации после-ности на языке программирования?

    и что такое перестановка?какое формальное значение вы определяете для данного слова?

    поясняю мой вопрос:
    пусть это кол-во чисел изменений полжений чисел относительно начального-
    тогда вы прстой операцией инкремента в строке точно не сможете определить это,
    надо учесть и просто изменение положения 2 чисел и изменения положения групп чисел(причём некоторые числа,входящие в группу могут не изменить своё начальное положение или вернуться на него) и т.д. я вообще сомневаюсь,что это реально сделать за хотя бы ту же трудоёмкость,что и саму сортировку
     
  3. MahovIV

    MahovIV New Member

    Регистрация:
    6 июл 2013
    Сообщения:
    2
    Симпатии:
    0
    Вы можете мне помочь?
     
  4. Whatka

    Whatka Well-Known Member

    Регистрация:
    9 окт 2011
    Сообщения:
    433
    Симпатии:
    4
    Да,если вы четко сформлируете своё задание
     
  5. MahovIV

    MahovIV New Member

    Регистрация:
    6 июл 2013
    Сообщения:
    2
    Симпатии:
    0
    Условие задачи:В этой задаче вам необходимо проанализировать некоторый алгоритм сортировки. Этот алгоритм сортирует последовательность из N различных целых чисел, переставляя по два соседних элемента последовательности до тех пор, пока она не будет упорядочена по возрастанию. Ваша задача состоит в том, чтобы посчитать, сколько таких перестановок двух соседних элементов необходимо сделать, чтобы отсортировать заданную последовательность.
    Я узнал, что нужно использовать сортировку слиянием.
     
  6. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Имеется ввиду перестановка двух любых элементов массива. Если элемент переставился, а потом вернулся назад - это 2 перестановки )
    Количество перестановок оценивают трудоемкость алгоритма, вот препод и хочет чтобы ТС посчитал это.

    вобще реально, но этоо не важно, задача ведь учебная )

    Сначала надо написать программу, которая просто сортирует массив, а уже потом вкручивать подсчет перестановок (сортировку можно найти на википедии), непойму в чем проблема.

    Но есть один момент:
    Чето я не пойму, как сортировка слиянием связана с перестановкой соседних элементов. И я не понял какой метод сортировки вы пытались в своем коде запилить.

    Про слияние тут прочитать можно: (хотя там реализация на Прологе и элементы в массивах вобще не переставляются) http://pro-prof.com/archives/846

    Суть слияния в том, что массив делится пополам, каждый из подмассивов делится еще раз пополам и т.п. до тех пор, пока массивы не станут достаточно маленькими. К маленьким массивам могут применяться любые алгоритмы сортировки. А потом отсортированные массивы начинаются сливаться в один большой отсортированный массив - и эта операция занимает кучу времени (только при этом происходят перестановки любых, а не только соседних элементов).

    Че вам посчитать то надо?
     
  7. MahovIV

    MahovIV New Member

    Регистрация:
    6 июл 2013
    Сообщения:
    2
    Симпатии:
    0
    Нужно посчитать перестановки соседних элементов.
     
  8. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Нужно - посчитай. Если есть конкретный вопрос - задавай.
     
Загрузка...
Похожие Темы - Сортировка Слиянием
  1. vera2014
    Ответов:
    0
    Просмотров:
    1.067
  2. Liori
    Ответов:
    2
    Просмотров:
    1.002
  3. FCDK
    Ответов:
    0
    Просмотров:
    1.260
  4. ленарано
    Ответов:
    1
    Просмотров:
    1.102
  5. Creder
    Ответов:
    0
    Просмотров:
    1.343

Поделиться этой страницей