Сортування злиттям Merge-sort в Java

Кожен програміст спочатку повинен продумати схему/план/архітектуру майбутньої роботи, інакше це вивалюється в кашу, з повною анархією. Як і в будь-якому своєму пості, спочатку потрібен план, почнемо.

• 1) Візьмемо тему сортування злиттям Merge для новачків.
• 2) Створимо архітектуру, план подальшої роботи.
• 3) Пропрацюємо та опишемо всі частини плану.
• 4) Перевіримо працездатність та якість.

• 2.1) Що таке сортування Merge?
• 2.2) Опис можливих сигнатур.
• 2.3) Навести приклад.
• 2.4) На прикладі описати реалізацію Java.
• 2.5) Щось додатково.

Merge - сортування злиттям у Java

Має на увазі принцип "поділяй і володарюй". У чому ідея та її зміст?

1. Сортування.

   Розділяємо масив на частини, поки він не дорівнюватиме 1 елементу. Кожен один елемент є відсортованим.

2. Злиття.

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

Витрачений час O(n log2 n). Сортування вважається досить швидким. Коротко про алгоритмічну складність, якщо комусь потрібно Часто можна побачити функції типу:

Sort(A, p, q);
Merge(A, p, q, r);

Це приблизно те саме, тільки прив'язане на індекси. Змінні в них це:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

Якщо ці змінні не описані, значить той, хто просить зробити таку функцію сам, не знає, чого хоче. А вам доведеться лопатити гугл у пошуках, що це таке, напевно знайдете, можливо. Наведемо приклад до нашого сортування. Є масив {6, 1, 3, 5, 2, 4, 7, 8}, якщо його довжина більше 1, то ми ділимо його на 2 частини та отримуємо ліву частину {6, 1, 3, 5}та праву частину {2, 4, 7, 8}. Продовжуємо дію розподілу на 2 частини, поки його довжина буде більше 1. У результаті отримаємо купу масивів довжиною в 1 елемент, а саме: {6} {1} {3} {5} {2} {4} {7} {8}. Реалізація на Java приблизно така:

public int [] sortArray(int[] arrayA){ // сортування Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 елемента в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

Далі потрібно злити ці масиви 1. Як це робиться? Щоб не проходити багаторазово по кожному масиву, введемо індекси позиції кожного масиву. Після чого один раз пройдемо по циклу, що дорівнює довжині суми цих двох масивів. Береться перший масив та другий масив, і береться перший елемент, порівнюється більше елемент номер 1 у першому масиві та елемент номер 1 у другому масиві? Найменший з них кладеться в результуючий масив. Тут важливо, якщо ми взяли елемент з першого масиву, то при переході циклу він повинен посилатися на 2 елемент першого масиву і на 1 елемент другого масиву. Для цього потрібно збільшити індекс другого масиву на +1 і при перевірці віднімати його з номера циклу, аналогічно для першого масиву. Зрозуміло навіщо це робити? Чи взагалі нічого не зрозуміло? :-) Наприклад є 2 масиви: {1}{4}{8}і {3}{6}{7} І є цикл:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

При першому проході циклу вийде arrayC[1] = {1}: ми взяли цей елемент з першого масиву. То при проході по другому циклу ми вже повинні порівнювати елемент {4}і {3}, але щоб це зробити нам потрібні враховувати індекси позицій і зміщення обох масивів, для цього вводимо їх.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

Але це ще не все, треба врахувати, що якийсь масив може закінчитись раніше. Наприклад, є 3 масиви: {1}{3}{5}і {6}{7}{9} Перший масив закінчиться ще до того, як підійде другий, для цього потрібно ввести перевірку і, в принципі, готова функція злиття.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

Найважче у цьому сортуванні – це принцип переходу рекурсії. Тобто. ми закидаємо в рекурсію ліву частину доти, доки вона ділиться на 2, а потім розкручуємо її назад, на словах це дуже складно та заплутано, а коли намагаєшся уявити, якщо ще й не зрозуміло, то зовсім ліс. Беремо масив: {2}{1}{4}{3}. Перша рекурсія сортування поділить його на 2 частини і запустить функцію ще раз з елементами 2-1 потім ще раз з елементом 2 і 1 поверне їх по черзі, таким чином у функцію злиття потраплять першими вони, а вийдуть вже 1-2 потім рекурсія повернеться назад і закине в злиття вже 4-3 , потім 4 і 3 , після чого злиття поверне 3-4, а потім рекурсія розкрутиться знову і у злиття потрапить вже 1-2 і 3-4 , а повернеться відсортований масив 1-2-3-4 . Ну ось загалом і все, сортування складається із двох функцій.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

Якщо записати якийсь мейн, вийде щось на кшталт:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

Для мене це сортування було повним провалом, питань було мільйон, а відповідей немає, я перекопав весь інтернет, перечитав, переглянув купу відео, але, як і завжди, відповіді знайшов лише сам. І тільки, коли почав писати рішення зовсім інше, ніж яке миготить скрізь) А в результаті вийшло схоже на всі інші))) Сортування насправді найпростіше, головне уявити інтерактивно її в дії, і все стає на свої місця, якщо руки дійдуть, зроблю відео)))) Поки що це все, на що мене вистачило: Сортування злиттям Merge-sort Найголовніше, завжди робіть план спочатку. Краще почекати і подумати, перш ніж почати щось робити. Нехай на це піде більше часу, але з'явиться розуміння і шлях вирішення, ніж доведеться переписувати кілька разів і вигадувати мабоці. Всім дякую, що приділабо час, удачі та гарного настрою. ) PS: Критика, хороше і погане, а також питання дуже вітаються. )))