Главная / Веб-программирование / Базы данных / Алгоритм сортировки слиянием

Алгоритм сортировки слиянием

Сортировка слиянием (merge sort) — один из самых популярных алгоритмов сортировки, который помогает освоить навыки составления рекурсивных алгоритмов.

Стратегия «разделяй и властвуй»

Применяя стратегию «разделяй и властвуй», мы делим задачу на подзадачи. Когда готово решение каждой подзадачи, их результаты объединяются, чтобы решить основную.

Предположим, нужно отсортировать массив A. Подзадачей будет сортировка подраздела этого массива, начиная с индекса p и заканчивая индексом r, обозначенного как A[p..r].

«Разделяй»

Если q — это точка на полпути между p и r, то подмассив A [p.. r] можно разделить на два массива: A [p.. q] и A [q + 1, r].

«Властвуй»

На этапе «властвуй» сортируем оба подмассива A[p..q] и A[q+1, r]. Если мы еще не достигли базового случая, снова разделяем эти подмассивы и сортируем.

Объединение

Если этап «завоевания» достигает базового, и для массива A[p..r] мы получаем два отсортированных подмассива A[p..q] и A[q+1, r], объединяем их результаты, создавая отсортированный массив A[p..r] из двух отсортированных A[p..q] и A[q+1, r]

Алгоритм MergeSort

В merge sort алгоритме одноименная функция делит массив на две половины пока не будет достигнут этап, где p == r.

После этого начинает действовать функция слияния. Она соединяет отсортированные массивы в более крупные пока не будет объединен весь массив.

MergeSort(A, p, r)
If p > r
return;
q = (p+r)/2;
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)

Чтобы отсортировать весь массив, нужно вызвать MergeSort(A, 0, length(A)-1).

Алгоритм сортировки слиянием

Как показано на рисунке, алгоритм сортировки слиянием рекурсивно делит массив пополам пока не будет достигнут базовый случай. Затем функция слияния собирает отсортированные подмассивы и объединяет их, чтобы отсортировать весь массив.

Алгоритм сортировки слиянием

Этап слияния

Наиболее важной частью алгоритма сортировки слиянием является этап слияния. Это решение простой задачи слияния двух отсортированных списков (массивов) для построения одного большого отсортированного.

Алгоритм merge sort C поддерживает три указателя: по одному для каждого из двух массивов, и один для текущего индекса окончательного отсортированного массива.

Алгоритм сортировки слияниемАлгоритм сортировки слиянием

Поскольку во втором массиве больше не осталось элементов, и известно, что оба массива были отсортированы при запуске, можно скопировать оставшиеся элементы из первого массива.

Написание кода для алгоритма слияния

Заметное различие между этапом слияния, описанным выше, и тем, который используется для merge sort, состоит в том, что функция слияния выполняется только для последовательных подмассивов. Вот почему нужен только массив, первая позиция, последний индекс первого подмассива (можно вычислить первый индекс второго подмассива) и последний индекс второго подмассива.

Наша задача состоит в объединении двух подмассивов A[p..q] и A[q+1..r], чтобы создать отсортированный массив A[p..r]. Таким образом, входными данными функции являются A, p, q и r.

Функция слияния работает следующим образом:

  • Создает копии подмассивов L <- A[p..q] и M <- A[q+1..r].
  • Создает три указателя i, j и k:
    • i сохраняет текущий индекс L, начиная с 1;
    • j сохраняет текущий индекс M, начиная с 1;
    • k сохраняет текущий индекс A[p..q], начиная с p.
  • Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M и помещаем их в нужной позиции в A[p..q]
  • Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..q]
  • В коде реализации merge sort алгоритма это будет выглядеть следующим образом:

    void merge(int A[], int p, int q, int r)
    {
    /* Создать L <- A[p..q] and M <- A[q+1..r] */
    int n1 = q — p + 1;
    int n2 = r — q;

    int L[n1], M[n2];

    for (i = 0; i < n1; i++)
    L[i] = A[p + i];
    for (j = 0; j < n2; j++)
    M[j] = A[q + 1 + j];

    /* Сохранить текущий индекс подмассивов и основной массив */
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    /*Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M, и помещаем их в нужной позиции в A[p..r] */
    while (i < n1 && j < n2)
    {
    if (L[i] <= M[j])
    {
    arr[k] = L[i];
    i++;
    }
    else
    {
    arr[k] = M[j];
    j++;
    }
    k++;
    }

    /* Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..r] */
    while (i < n1)
    {
    A[k] = L[i];
    i++;
    k++;
    }

    while (j < n2)
    {
    A[k] = M[j];
    j++;
    k++;
    }
    }

    Пошаговое пояснение функции слияния

    Рассмотрим пример merge sort, который покажет, как это все работает:

    Алгоритм сортировки слиянием

    Массив A[0..8] содержит два отсортированных подмассива A[1..5] и A[6..7]. Рассмотрим, как функция слияния объединяет два массива.

    void merge(int A[], int p = 1, int q = 4, int 6)
    {

    Шаг 1: Создать повторяющиеся копии подмассивов для сортировки

    /* Создать L <- A[p..q] and M <- A[q+1..r] */
    n1 = 4 — 1 + 1 = 4;
    n2 = 6 — 4 = 2;

    int L[4], M[2];

    for (i = 0; i < 4; i++)
    L[i] = A[p + i];
    /* L[0,1,2,3] = A[1,2,3,4] = [1,5,10,12] */

    for (j = 0; j < 2; j++)
    M[j] = A[q + 1 + j];
    /* M[0,1,2,3] = A[5,6] = [6,9]Алгоритм сортировки слиянием

    Шаг 2: Сохранить текущий индекс подмассивов и основной массив merge sort C

    int i, j, k;
    i = 0;
    j = 0;
    k = p;Алгоритм сортировки слиянием

    Шаг 3: Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M, и помещаем их в нужной позиции в A[p..r]

    while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
    A[k] = L[i]; i++;
    }
    else {
    A[k] = M[j];
    j++;
    }
    k++;
    }Алгоритм сортировки слиянием

    Шаг 4: Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..r]

    /* Выходим из предыдущего цикла, поскольку i < n1 не поддерживается */
    while (i < n1)
    {
    A[k] = L[i];
    i++;
    k++;
    }Алгоритм сортировки слиянием/* Выходим из предыдущего цикла, поскольку i < n1 не поддерживается */
    while (i < n1)
    {
    A[k] = L[i];
    i++;
    k++;
    }Алгоритм сортировки слиянием

    В примере merge sort алгоритма этот шаг необходим, если размер M был больше L. В конце функции слияния подмассив A[p..r] является отсортированным.

    Перевод статьи “Merge Sort Algorithm” был подготовлен дружной командой проекта Сайтостроение от А до Я.

    О нас seoexpert

    продвижение сайта,seo оптимизация,поисковое продвижение,раскрутка сайтов,поисковая оптимизация,продвижение сайта в гугл,seo раскрутка,продвижение сайтов в яндексе,продвижение сайта в google,продвижение сайтов в топ 10,Оптимизация и продвижение сайтов,услуги продвижения сайта,заказать продвижение,продвижение сайтов в топ,сео раскрутка сайта

    Смотрите также

    Установка PostgreSQL — Windows, Mac OS X, Linux

    Для Microsoft Windows, Mac OS X и Linux существует один установщик. Его можно скачать здесь. ...