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

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

Сортировка слиянием — это довольно быстрая сортировка, время работы которой О(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 Replies to “Сортировка слиянием на С++”

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

  2. Viktor,

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

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

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

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

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

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *