Сбалансированное слияние сверху-вниз и снизу-вверх
В прошлой статье мы ознакомились с реликтовыми сортировками слияния (вызывающих прежде всего исторический интерес). А что в тренде сегодня?
Для ознакомления с концепцией упорядочивания через слияния обычно используются алгоритмы сбалансированного слияния. Термин «сбалансированность» означает, что алгоритм рекурсивно разбивает массив и его подмассивы на примерно равные части. Сегодня мы рассмотрим как это выглядит на практике.
Пара функций одинакова для обоих методов. Да и вообще, что «вниз-вверх», что «вверх-вниз» — это практически один и тот же алгоритм, просто показанный с разных ракурсов.
Нам, понадобится, собственно, слияние двух половинок отрезка в один подмассив. Половинки одновременно перебираются в одном массиве, сравниваются текущие элементы в обоих переборах и меньший элемент уходит во второй массив:
//Левая половина источника A[iBegin: iMiddle - 1]
//Правая половина источника A[iMiddle: iEnd - 1]
//Результат: слияние в B[iBegin: iEnd - 1]
void Merge(A[], iBegin, iMiddle, iEnd, B[]) {
i = iBegin, j = iMiddle;
//Пока есть элементы в левом или правом прогоне...
for (k = iBegin; k < iEnd; k++) {
//Если левый указатель ещё существует
//и он <= существующего правого указателя
if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
B[k] = A[i];
i++;
} else {
B[k] = A[j];
j++;
}
}
}
Копирование отрезка из одного массива в другой. Обе реализации оперируют двумя массивами, данные приходится постоянно гонять из основного во вспомогательный и обратно:
//Копируем из основного массива A[]
//во вспомогательный массив B[]
void CopyArray(A[], iBegin, iEnd, B[]) {
for(k = iBegin; k < iEnd; k++) B[k] = A[k];
}
Сначала берётся весь массив целиком, после чего начинается рекурсивный спуск. Массив дихотомируется до тех пор, пока не дойдём до подмассивов из одного элемента (которые являются отсортированными сами по себе). Затем рекурсия начинает обратный подъём, производя по пути слияние подмассивов (размер которых на каждом уровне удваивается).
//Основной массив A[] содержит элементы для сортировки
//Массив B[] является вспомогательным
void TopDownMergeSort(A[], B[], n) {
CopyArray(A, 0, n, B); //Дублируем A[] в B[]
TopDownSplitMerge(B, 0, n, A);//Сортируем B[] и возвращаем в A[]
}
//Сортировка заданного прогона для A[], используя B[] в качестве источника
//Границы диапазона: iBegin включительно; iEnd не включая
void TopDownSplitMerge(B[], iBegin, iEnd, A[]) {
//Если size == 1, то такой подмассив отсортирован
if(iEnd - iBegin < 2) return;
//Если size > 1, такие массивы делим пополам
iMiddle = (iEnd + iBegin) / 2;//iMiddle - середина отрезка
//Рекурсивно сортируем обе половины из A[] в B[]
TopDownSplitMerge(A, iBegin, iMiddle, B);//Сортируем левую половину
TopDownSplitMerge(A, iMiddle, iEnd, B);//Сортируем правую половину
//Объединяем полученные прогоны из B[] в A[]
Merge(B, iBegin, iMiddle, iEnd, A);
}
Здесь происходит итерация по массиву, по пути сначала берём соседние минимальные массивы (из одного элемента) и попарно производим их слияние. Получая на каждом шаге удвоенные отсортированные подмассивы, снова производим слияние соседей и так продолжаем до тех пор, пока на выходе не получим весь массив, уже в отсортированном виде.
//Основной массив A[] содержит элементы для сортировки
//Массив B[] является вспомогательным
void BottomUpMergeSort(A[], B[], n) {
//Каждый подмассив из одного элемента в A[] уже «отсортирован».
//Последовательные отсортированные прогоны удваивающейся длины:
//× 2, 4, 8, 16, ... - до тех пор, пока не будет отсортирован весь массив
for (width = 1; width < n; width = 2 * width) {
//Массив А заполнен прогонами длиной width
for (i = 0; i < n; i = i + 2 * width) {
// Объединение двух прогонов:
//A [i: i + width - 1] и A [i + width: i + 2 * width - 1] в B[]
//или копирование A[i: n - 1] в B[] (если i + width > = n)
Merge(A, i, min(i + width, n), min(i + 2 * width, n), B);
}
//Теперь вспомогательный массив B[] заполнен прогонами длиной 2 * width
//Копируем массив B[] в массив A[] для следующей итерации
//Более эффективная реализация меняет роли A[] и B[]
CopyArray(B, 0, n, A); //Возвращаем B[] в A[]
//Теперь массив А заполнен прогонами длиной 2 * width
}
}
В целом предпочтительнее нисходящая реализация, так как в ней эффективнее используются два массива, которые просто постоянно меняются ролями «основной/вспомогательный». В восходящем варианте массив A всегда основной, а массив B всегда вспомогательный. В результате, после каждой итерации данные из B нужно в полном составе возвращать в A, что не способствует улучшению алгоритмической сложности. С другой стороны, реализация восходящей проще, в ней даже нет рекурсии.
От самого слова «сбалансированность» веет какой-то надёжностью, устойчивостью. Может даже создаться впечатление, что хороший алгоритм должен быть непременно сбалансированным. А «несбалансированность» ассоциируется с какой-то нестабильностью, расшатанностью. Ну действительно, разве сбалансированное не должно быть во всех отношениях лучше чем несбалансированное?
На самом деле, бывает что и хуже. Само собой, разделение подмассивов на равные половины (что и подразумеваются под сбалансированностью для сортировок слиянием) гораздо проще реализовать. Дели себе массив напополам и к каждой половине применяй рекурсию. Собственно, в этой лёгкости и заключается основное достоинство сбалансированного слияния перед несбалансированным.
В следующих публикациях мы ознакомимся с несбалансированными способами. Они заметно сложнее в понимании и реализации. Данные для последующего слияния будут распределяться по вспомогательным массивам не равномерно да поровну, а в соответствии с рядом обобщённых чисел Фибоначчи. И это позволит достигать мощных результатов, которые недостижимы для упрощённых сбалансированных методов.
Ссылки
Merge (Google-translate), Слияние
Статьи серии:
Очередные слиятельные сортировки теперь доступны в приложении AlgoLab (кто изучает алгоритмы с помощью этого Excel-приложения — обновите файл). И это далеко не последние сортировки слиянием, которые добавятся на этой неделе.
Временно на массивы поставлено ограничение — их размер должен быть степенью двойки (связано с некоторыми сложностями, возникшими при программировании визуализации). Чуть позже можно будет сортировать любые массивы.
Статья написана при поддержке компании EDISON Software, которая с помощью облачных сервисов создаёт встроенное программное обеспечение и разрабатывает мобильные приложения на JAVA.
