
Сортировка слиянием на С++
Сортировка слиянием — это довольно быстрая сортировка, время работы которой О(n * log n). Однако ее недостатком является тот факт, что она требует относительно много памяти.
Итак, пусть дан некоторый неупорядоченный массив int a[maxn].
Основная идея состоит в том, что на каждом шагу мы разбиваем массив на 2 равные части, сортируем их, а потом сливаем два отсортированных куска. То есть получается рекурсивная сортировка, т.к. каждую из этих 2 частей мы будем сортировать аналогично. Выход из рекурсии будет происходить тогда, когда у нас остается меньше 3 элементов. Если их остается всего 2, то меняем их между собой по мере надобности. Если остается только 1 элемент, то оставляем его в покое.
Пример. Пусть дан исходный массив из 7 элементов:
- 7 4 2 1 0 5 3
- Шаг 0: 7 4 2 1 0 5 3
- Шаг 1: 4 7 2 1 0 5 3
- Шаг 2: 4 7 1 2 0 5 3
- Шаг 3: 1 2 4 7 0 5 3
- Шаг 4: 1 2 4 7 0 3 5
- Шаг 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;
}
Viktor
26.05.2013 20:08Всем доброго времени суток в данном коде нужна помощь), необходимо вывести весь ход сортировки на экран от начальных значений до конечных,то есть как сортирует этот алгоритм.Заранее благодарен!
Mr.Cheater
27.05.2013 20:08Viktor,
Для того, чтобы понять как сортирует этот алгоритм, необходимо прежде всего прочесть статью
ну а для того, чтобы выводить промежуточные значения добавьте
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 + программка