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

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

Сортировка слиянием — это довольно быстрая сортировка, время работы которой О(n * log n). Однако ее недостатком является тот факт, что она требует относительно много памяти.

Итак, пусть дан некоторый неупорядоченный массив int a[maxn].

Основная идея состоит в том, что на каждом шагу мы разбиваем массив на 2 равные части, сортируем их, а потом сливаем два отсортированных куска. То есть получается рекурсивная сортировка, т.к. каждую из этих 2 частей мы будем сортировать аналогично. Выход из рекурсии будет происходить тогда, когда у нас остается меньше 3 элементов. Если их остается всего 2, то меняем их между собой по мере надобности. Если остается только 1 элемент, то оставляем его в покое.

Пример. Пусть дан исходный массив из 7 элементов:

  1. 7 4 2 1 0 5 3
  2. Шаг 0: 7 4 2 1 0 5 3
  3. Шаг 1: 4 7 2 1 0 5 3
  4. Шаг 2: 4 7 1 2 0 5 3
  5. Шаг 3: 1 2 4 7 0 5 3
  6. Шаг 4: 1 2 4 7 0 3 5
  7. Шаг 5: 0 1 2 3 4 5 7

Рассмотрим каждый шаг подробно.

Шаг 1:
Сначала рекурсия спустится максимально глубоко, то есть до элементов a[0] и a[1]. Так как 7 > 4, то они поменяются местами.

Шаг 2:

Дальше смотрим на элементы a[3] и a[4]. Так как они тоже стоят неправильно, то меняем их местами.

Шаг 3:

Сейчас крайними являются элементы с индексами 0 и 3. У нас есть 2 отсортированные части. Осталось их слить, чтобы кусок от a[0] до a[3] стал отсортированным. Для этого заведем дополнительный массив buf, куда будем записывать минимальный элемент из левой и правой части. Так как они уже отсортированы, то будем сравнивать самые левые элементы. Так как
1 < 4, то в buf отправится 1. Дальше, по тем же соображениям в buf отправляется 2. Так как в правой части элементы закончились, то в buf отправляются элементы 4 и 7. Теперь когда buf сформирован, помещаем его тсодержимое в массив a.

Шаг 4:

Аналогично поступаем с правой частью, т.е. с куском массива и индексами от 4 до 6.

Шаг 5:

Сливаем левую и правую части. Получаем отсортированный массив.

И картинка для еще большей наглядности:

Код:

#include <iostream>
#include <conio.h>

using namespace std;

#define maxn 100

int a[maxn];

int n;

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++];
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);

for (int i = 0; i < n; i++)
cout << a[i] << » «;

getch();
return 0;
}

8 комментариев

  • Viktor

    Ответить 26.05.2013 20:08

    Всем доброго времени суток в данном коде нужна помощь), необходимо вывести весь ход сортировки на экран от начальных значений до конечных,то есть как сортирует этот алгоритм.Заранее благодарен!

  • Mr.Cheater

    Ответить 27.05.2013 20:08

    Viktor,

    Для того, чтобы понять как сортирует этот алгоритм, необходимо прежде всего прочесть статью

    ну а для того, чтобы выводить промежуточные значения добавьте
    for (int i = 0; i < n; i++)
    cout << a[i] << " ";

    перед строкой
    if (r == l)

  • Viktor

    Ответить 27.05.2013 20:09

    Спасибо большое,сидел вникал понял,но чуть по другому написал,пробую ваш вариант=)

  • Руслан

    Ответить 08.09.2013 20:09

    Как посчитать количество перестановок?

  • Елена

    Ответить 08.11.2013 20:09

    Не могли бы вы подробно описать начинающему действия по данной программе?

  • Mr.Cheater

    Ответить 12.11.2013 20:10

    Цитата: Елена:
    «Не могли бы вы подробно описать начинающему действия по данной программе?»

    В статье и расписывается подробно алгоритм.

  • Igrina

    Ответить 05.05.2014 20:10

    Хочу видеть промежуточные значения, добавила
    for (int i = 0; i < n; i++)
    cout << a[i] << " "; перед строкой
    if (r == l), но результат не вижу. Помогите пожалуйста, только начинаю изучать сортировки

  • Андрей

    Ответить 03.10.2014 20:11

    Вот,здесь подробно описано об этом http://orenstudent.ru/mergesort2.htm + программка

Оставить комментарий