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

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


Сортировка слиянием - это довольно быстрая сортировка, время работы которой О(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;
}
Ключевые теги: Сортировка слиянием С
Понравилась новость? Добавь в закладки!
Хочешь получать свежие новости? Подпишись на обновления с сайта!
Рекомендуем посмотреть:
#1 | написал: Viktor | 26 мая 2013 21:41 | ICQ: |

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

#2 | написал: Mr.Cheater | 27 мая 2013 17:12 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68
Viktor,

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

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

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



#3 | написал: Viktor | 27 мая 2013 23:39 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
Спасибо большое,сидел вникал понял,но чуть по другому написал,пробую ваш вариант=)

#4 | написал: Руслан | 8 сентября 2013 21:09 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
Как посчитать количество перестановок?

#5 | написал: Елена | 8 ноября 2013 00:43 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
Не могли бы вы подробно описать начинающему действия по данной программе?

#6 | написал: Mr.Cheater | 12 ноября 2013 14:00 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68
Цитата: Елена
Не могли бы вы подробно описать начинающему действия по данной программе?

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

#7 | написал: Igrina | 5 мая 2014 16:29 | ICQ: |

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

#8 | написал: Андрей | 3 октября 2014 19:02 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
Вот,здесь подробно описано об этом http://orenstudent.ru/mergesort2.htm + программка

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

Ваше Имя:
Ваш E-Mail:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Вставка исходного кода Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера

Введите два слова, показанных на изображении: