Lila25mila
Lila25mila6 марта 2019 г. 3:49

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

Сортировка слиянием - это своего рода алгоритм «разделяй и властвуй» в компьютерном программировании. Это один из самых популярных алгоритмов сортировки и отличный способ развить уверенность в построении рекурсивных алгоритмов.


Стратегия "Разделяй и влавствуй"

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

Предположим, нам нужно было отсортировать массив 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..q] и A [q + 1, r] для массива A [p..r], мы объединяем результаты, создавая отсортированный массив A [p..r] из двух отсортированных подмассивов A [p..q] и A [q + 1, r]

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

Функция MergeSort многократно делит массив на две половины, пока мы не достигнем стадии, когда мы пытаемся выполнить MergeSort для подмассива размером 1, т.е. 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).
Как показано на рисунке ниже, алгоритм сортировки слиянием рекурсивно делит массив на две половины, пока мы не достигнем базового случая массива с 1 элементом. После этого функция слияния выбирает отсортированные подмассивы и объединяет их для постепенной сортировки всего массива.

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

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

Шаг объединения - это решение простой проблемы объединения двух отсортированных списков (массивов) для создания одного большого отсортированного списка (массива).

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

Достигли ли мы конца какого-либо из массивов?
    Нет:
        Сравните текущие элементы обоих массивов
        Скопируйте меньший элемент в отсортированный массив
        Переместить указатель на элемент, содержащий меньший элемент
    Да:
        Скопировать все оставшиеся элементы непустого массива

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

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

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

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

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

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

  1. Создайте копии подмассивов L ← A [p..q] и M ← A [q + 1..r].
  2. Создайте три указателя i, j и k
    1. i поддерживает текущий индекс L, начиная с 1
    2. j поддерживает текущий индекс М, начиная с 1
    3. k поддерживает текущий индекс A [p..q], начиная с p
  3. Пока мы не достигнем конца L или M, выберите больший из элементов из L и M и поместите их в правильное положение в A [p..q]
  4. Когда у нас кончаются элементы в L или M, возьмите оставшиеся элементы и поместите в A [p..q]

В коде это будет выглядеть так:

void merge(int A[], int p, int q, int r)
{
    /* Создание L ← A[p..q] и 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++;
    }
}
Функция слияния пошагово

В этой функции много действий, поэтому давайте рассмотрим пример, чтобы увидеть, как это будет работать.

Массив 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] и 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: Поддержание текущего индекса подмассивов и основного массива
 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]
/* Мы вышли из предыдущего цикла, потому что j <n2 не выполняется */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

/* Мы вышли из предыдущего цикла, потому что i <n1 не выполняется */  

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

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

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Вам это нравится? Поделитесь в социальных сетях!

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:50баллов,
  • Очки рейтинга-4
m
  • molni99
  • 26 октября 2024 г. 11:37

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:80баллов,
  • Очки рейтинга4
m
  • molni99
  • 26 октября 2024 г. 11:29

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:20баллов,
  • Очки рейтинга-10
Последние комментарии
i
innorwall14 ноября 2024 г. 22:42
Как Копировать Файлы в Linux If only females relatives with DZ offspring were considered these percentages were 23 order priligy online uk
i
innorwall14 ноября 2024 г. 20:09
Qt/C++ - Урок 068. Hello World с использованием системы сборки CMAKE в CLion ditropan pristiq dosing With the Yankees leading, 4 3, Rivera jogged in from the bullpen to a standing ovation as he prepared for his final appearance in Chicago buy priligy pakistan
i
innorwall14 ноября 2024 г. 15:05
EVILEG-CORE. Использование Google reCAPTCHA 2001; 98 29 34 priligy buy
i
innorwall14 ноября 2024 г. 15:00
PyQt5 - Урок 007. Работаем с QML QtQuick (Сигналы и слоты) priligy 30mg Am J Obstet Gynecol 171 1488 505
Сейчас обсуждают на форуме
i
innorwall14 ноября 2024 г. 14:39
добавить qlineseries в функции priligy amazon canada 93 GREB1 protein GREB1 AB011147 6
i
innorwall11 ноября 2024 г. 21:55
Всё ещё разбираюсь с кешем. priligy walgreens levitra dulcolax carbs The third ring was found to be made up of ultra relativistic electrons, which are also present in both the outer and inner rings
9
9Anonim25 октября 2024 г. 19:10
Машина тьюринга // Начальное состояние 0 0, ,<,1 // Переход в состояние 1 при пустом символе 0,0,>,0 // Остаемся в состоянии 0, двигаясь вправо при встрече 0 0,1,>…
ИМ
Игорь Максимов3 октября 2024 г. 14:05
Реализация навигации по разделам Спасибо Евгений!

Следите за нами в социальных сетях