- 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).
Как показано на рисунке ниже, алгоритм сортировки слиянием рекурсивно делит массив на две половины, пока мы не достигнем базового случая массива с 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] сортируется.