- 1. Стратегія розділяй і володарюй
- 1. Поділитися
- 2. Влавствуй
- 3. Комбінуємо
- 2. Алгоритм сортування злиттям
- 3. Крок злиття сортування злиттям
- 4. Написання коду для алгоритму злиття
- 5. Функція злиття покроково
- 1. Крок 1. Створіть дублікати копій підмасивів для сортування
- 2. Крок 2: Підтримка поточного індексу підмасивів та основного масиву
- 3. Крок 3: Поки ми не досягнуть кінець L або M, вибирається більше серед елементів L і M і поміщається в правильне положення в точці A [p..r]
- 4. Крок 4: Коли закінчуються елементи в L або M, елементи, що залишилися, необхідно помістити в A [p..r]
Сортування злиттям – це свого роду алгоритм «розділяй і володарюй» у комп'ютерному програмуванні. Це один із найпопулярніших алгоритмів сортування та відмінний спосіб розвинути впевненість у побудові рекурсивних алгоритмів.
Стратегія розділяй і володарюй
Використовуючи техніку «Розділяй і володарюй», ми ділимо проблему на підзавдання. Коли рішення для кожного підзавдання готове, ми об'єднуємо результати з підзавдань, щоб вирішити основну проблему.
Припустимо, нам потрібно було відсортувати масив 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
Функція злиття працює наступним чином:
- Створіть копії підмасивів L ← A [p..q] та M ← A [q + 1..r].
- Створіть три покажчики i, j та k
- i підтримує поточний індекс L, починаючи з 1
- j підтримує поточний індекс М, починаючи з 1
- k підтримує поточний індекс A [p..q], починаючи з p
- Доки ми не досягнемо кінця L або M, виберіть більший з елементів з L і M і помістіть їх у правильне положення в A [p..q]
- Коли у нас закінчуються елементи в 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] сортується.