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

алгоритм, сортировка слиянием, Merge Sort Algorithm, сортировка

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

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

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

Предположим, нам нужно было отсортировать массив 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] сортируется.

Возврат 10% от суммы заказа отеля на Booking
Возврат 10% от суммы заказа отеля на Booking
Предлагаем ссылку с 10% возвратом от суммы заказа при бронировании отеля через Booking

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
s
26 мая 2019 г. 14:33
simpleunderground

Qt - Тест 001. Сигналы и слоты

  • Результат:31баллов,
  • Очки рейтинга-10
НД
25 мая 2019 г. 23:25
Николай Демиденко

C++ - Тест 003. Условия и циклы

  • Результат:64баллов,
  • Очки рейтинга-1
НД
25 мая 2019 г. 23:19
Николай Демиденко

C++ - Тест 002. Константы

  • Результат:50баллов,
  • Очки рейтинга-4
Последние комментарии
21 мая 2019 г. 20:10
Дмитрий

Приветствую! Я думаю дойдёт и до этого, но пока изучать его у меня нет желания.
20 мая 2019 г. 19:20
Евгений Легоцкой

Добрый день! Вы не думали разместить репозиторий проекта на GitHub?
P.
18 мая 2019 г. 14:03
PELMYACH .

Спасибо большое! Вскоре буду разбираться!
18 мая 2019 г. 9:13
Евгений Легоцкой

Добрый день! Отнимать значение общего счётчика можно в деструкторе класса кнопки QDynamicButton::~QDynamicButton(){ ResID--;} При этом я бы ещё переустанавливал значения вс...
P.
14 мая 2019 г. 22:33
PELMYACH .

Здравствуйте!А не подскажите, как можно при удалении какой либо кнопки, у щётчика отнять значение?Дабы например четвёртой кнопке соответствовал ID 4, а не 5 скажем
Сейчас обсуждают на форуме
26 мая 2019 г. 6:49
Михаиллл

Скачал dll от сюда и заработало
24 мая 2019 г. 6:48
Евгений Легоцкой

Если там будут только перечисления внутри namespace, то жа, достаточно будет заголовочного файла
24 мая 2019 г. 6:28
Андрей Янкович

работает любой http сервер, и можно использовать обсалютно любой портпример <RemoteRepositories> <Repository> <Url>http://178.124.160.6:3030/A/B&l...;
23 мая 2019 г. 10:42
Михаиллл

Спасибо, помогло.
23 мая 2019 г. 6:31
Евгений Легоцкой

Для задач и граф-то не нужен. Достаточно будет таблицы в локальной базе данных SQLite, в которой указывается задача, время и т.д. В этом разделе есть примеры по работа с базой д...

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

EVILEG
О нас
Услуги
Присоединяйтесь к нам
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB