Lila25mila
Lila25mila06 березня 2019 р. 03: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).
Як показано на малюнку нижче, алгоритм сортування злиттям рекурсивно ділить масив на дві половини, поки ми не досягнемо базового випадку масиву з одним елементом. Після цього функція злиття вибирає відсортовані підмасиви та поєднує їх для поступового сортування всього масиву.

Крок злиття сортування злиттям

Кожен рекурсивний алгоритм залежить від базового випадку та здатності комбінувати результати з базових випадків. не є винятком та сортування злиттям. Найважливіша частина алгоритму – крок «злиття».

Крок об'єднання – це вирішення простої проблеми об'єднання двох відсортованих списків (масивів) для створення одного великого відсортованого списку (масиву).

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

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

Оскільки в другому масиві більше не залишилося елементів, і ми знаємо, що обидва масиви були відсортовані при запуску, ми можемо скопіювати елементи з першого масиву безпосередньо

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

Помітна різниця між етапом злиття, який ми описали вище, і тим, що ми використовуємо для сортування злиттям, полягає в тому, що функція злиття виконується лише для послідовних підмасивів.

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

Наше завдання – об'єднати два підмасиви 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
  3. i підтримує поточний індекс L, починаючи з 1
  4. j підтримує поточний індекс М, починаючи з 1
  5. k підтримує поточний індекс A [p..q], починаючи з p
  6. Доки ми не досягнемо кінця L або M, виберіть більший з елементів з L і M і помістіть їх у правильне положення в A [p..q]
  7. Коли у нас закінчуються елементи в 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 хостинг.

Вам це подобається? Поділіться в соціальних мережах!

Коментарі

Only authorized users can post comments.
Please, Log in or Sign up
AD

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

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

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

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

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

  • Результат:20бали,
  • Рейтинг балів-10
Останні коментарі
ИМ
Игорь Максимов22 листопада 2024 р. 11:51
Django - Підручник 017. Налаштуйте сторінку входу до Django Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii Legotckoi31 жовтня 2024 р. 14:37
Django - Урок 064. Як написати розширення для Python Markdown Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZE19 жовтня 2024 р. 08:19
Читалка файлів fb3 на Qt Creator Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь Максимов05 жовтня 2024 р. 07:51
Django - Урок 064. Як написати розширення для Python Markdown Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas505 липня 2024 р. 11:02
QML - Урок 016. База даних SQLite та робота з нею в QML Qt Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Тепер обговоріть на форумі
Evgenii Legotckoi
Evgenii Legotckoi24 червня 2024 р. 15:11
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey115 листопада 2024 р. 06:04
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProject04 червня 2022 р. 03:49
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…
9
9Anonim25 жовтня 2024 р. 09:10
Машина тьюринга // Начальное состояние 0 0, ,<,1 // Переход в состояние 1 при пустом символе 0,0,>,0 // Остаемся в состоянии 0, двигаясь вправо при встрече 0 0,1,>…

Слідкуйте за нами в соціальних мережах