Сортування злиттям: алгоритм, переваги і особливості

Кучер В.Г.

Злиття відсортованих ділянок

Для розуміння алгоритму почнемо його розбір з кінця – з механізму злиття відсортованих блоків.

Уявімо, що у нас є два будь-яким способом відсортованого масиву чисел, які необхідно об’єднати один з одним так, щоб сортування не порушилася. Для простоти будемо впорядковувати числа за зростанням.

Елементарний приклад: обидва масиви складаються з одного елемента кожен.

int[] arr1 = {31};
int[] arr2 = {18};

Щоб злити їх, потрібно взяти нульовий елемент першого масиву (не забудьте, що нумерація починається з нуля) і нульовий елемент другого масивів. Це, відповідно, 31 і 18. За умовою сортування число 18 має йти першим, так як воно менше. Просто розставляємо числа в правильному порядку:

int[] result = {18, 31};

Звернемося до прикладу складніше, в якому кожен масив складається з декількох елементів:

int[] arr1 = {2, 17, 19, 45};
int[] arr2 = {5, 6, 21, 30};

Алгоритм злиття буде полягати в послідовному порівнянні менших елементів і розміщення їх у результуючому масиві в правильному порядку. Для відстеження поточних індексів введемо дві змінні – index1 і index2. Спочатку приравняем їх до нуля, так як масиви відсортовані, і найменші елементи стоять на початку.

int index1 = 0;
int index2 = 0;

Розпишемо по кроках весь процес злиття:

  • Беремо з масиву arr1 елемент з індексом index1, а з масиву arr2 – з індексом index2.
  • Порівнюємо, вибираємо найменшу з них і поміщаємо в результуючий масив.
  • Збільшуємо поточний індекс меншого елемента на 1.
  • Продовжуємо з першого кроку.

    • На першому витку ситуація буде виглядати так:

    index1 = 0;
    index2 = 0;
    arr1[0] = 2;
    arr2[0] = 5;
    arr1[0] < arr2[0];
    index1++;
    result[0] = arr1[0]; // result = [2]

    Цікаве:  Генеративна лінгвістика: що вивчає, цілі і результати

    На другому витку:

    index1 = 1;
    index2 = 0;
    arr1[1] = 17;
    arr2[0] = 5;
    arr1[1] > arr2[0];
    index2++;
    result[1] = arr2[0]; // result = [2, 5]

    На третьому:

    index1 = 1;
    index2 = 1;
    arr1[1] = 17;
    arr2[1] = 6;
    arr1[1] > arr2[1];
    index2++;
    result[2] = arr2[1]; // result = [2, 5, 6]

    І так далі, поки в результаті не вийде повністю результуючий масив відсортований: {2, 5, 6, 17, 21, 19, 30, 45}.

    Певні складності можуть виникнути, якщо зливаються масиви з різними довжинами. Що робити, якщо один з поточних індексів досяг останнього елемента, а у другому масиві ще залишаються члени?

    int[] arr1 = {1, 4};
    int[] arr2 = {2, 5, 6, 7, 9};
    // 1 step
    index1 = 0, index2 = 0;
    1 2
    result = {1, 2};
    // 3 step
    index1 = 1, index2 = 1;
    4 < 5
    result = {1, 2, 4};
    //4 step
    index1 = 2, index2 = 1
    ??

    Змінна index1 досягла значення 2, проте масив arr1 не має елемента з таким індексом. Тут все просто: достатньо перенести залишилися елементи другого масиву в результуючий, зберігши їх порядок.

    result = {1, 2, 4, 5, 6, 7, 9};

    Ця ситуація вказує нам на необхідність зіставляти поточний індекс перевірки з довжиною сливаемого масиву.

    Схема злиття упорядкованих послідовностей (A і B) різної довжини:

    • Якщо довжина обох послідовностей більше 0, порівняти A[0] і B[0] і перемістити менший з них в буфер.
    • Якщо довжина однієї з послідовностей дорівнює 0, взяти залишилися елементи другої послідовності і, не змінюючи їх порядок, перенести в кінець буфера.
    Сторінка: 1 2 3 4 5 6 7 8 9 10