...any scientist who couldn't explain to an eight-year-old what he was doing was a charlatan.
Оказывается, это был Курт Воннегут.
Я не стремился доказать это высказывание. Я стремился опровергнуть свою тупость.
Допустим у нас есть два массива чисел, отсортированных по возрастанию.
int[] a1 = new int[] {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500};
int[] a2 = new int[] {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
Необходимо слить их в один упорядоченный массив.
int[] a3 = new int[a1.length + a2.length];
Это задача для сортировки слиянием.
Что это такое? В интернете есть ответ, есть описание алгоритма, но я его не понял с одного присеста и решил разобраться сам. Для этого необходимо понять базовый принцип алгоритма, чтобы можно было по памяти воссоздать алгоритм применительно к своей задаче.
Начали за здравие
Давайте пойдем постепенно и воспользуемся тем, что лежит на поверхности: будем брать поочередно по одному элементу из каждого массива, сравнивать их и «сливать» в один массив. Меньший элемент будем ставить первым, больший – вторым. Тогда после первого прохода все нормально:
10, 21
А после второго прохода уже не очень:
10, 21, 11, 23
Понятно, что надо сравнивать элементы еще и с уже добавленными.
Начнем еще раз
Пусть у нас будет некий временный буфер из сравниваемых на каждом шаге элементов. После первого прохода в него попадут 21 и 10. После сравнения мы переместим из буфера в результирующий массив меньший элемент 10 и оставим больший элемент 21, потому что не знаем, что будет за ним.
После второго прохода в буфере будет 21, 23 и 11. Что с ними делать – непонятно, сравнить более двух элементов можно, но уже не так просто.
Давайте тогда условимся, что будем брать в этот буфер по одному элементу от каждого массива. Так как проще сравнивать два элемента между собой, да и вообще у нас две сущности – два массива. Тогда после второго прохода в буфере будет 21 и 11, потому что «представитель» первого массива в буфере уже есть – это 21. Сравниваем их и меньший отправляем в результирующий массив. Тогда после второго прохода будем иметь в результирующем массиве:
10, 11
А в буфере – 21.
На третьем проходе берем в буфер из второго массива 41, потому что «представитель» первого массива в буфере так и остался. Сравниваем 21 и 41, и наконец-то убираем из буфера 21.
После третьего прохода будем иметь в результирующем массиве:
10, 11, 21
На четвертом проходе будем сравнивать два значения из буфера — 41 и 23. В результирующем массиве будет:
10, 11, 21, 23
То есть только сейчас – на четвертом, а не на втором проходе — результат получился правильным. Получается, что в цикле надо помнить текущий индекс для каждого массива, а сам цикл может быть длиной равной сумме длин массивов.
Подходим к концу, но вдруг
Что будем делать, когда результирующий массив будет состоять из:
10, 11, 21, 23, 24, 40, 41, 50, 65, 75, 76, 78, 77, 86, 98, 101, 190, 900, 1100, 1200, 2100, 2200, 2300, 2400, 2500,
В буфере будет 3000 из второго массива, а в первом — все элементы кончатся? Так как массивы у нас отсортированы, то просто берем 3000 из буфера и оставшееся 5000. То есть нужно для каждого индекса выполнять проверку – не превысили ли мы количество элементов в каждом из массивов.
Усложним задачу
А если у нас не отсортированные массивы? Обычно задача сводится к тому, чтобы отсортировать один массив. Тогда сортировка слиянием тоже может быть использована.
Пусть первый массив (для примера возьмем из него несколько элементов) имеет следующее расположение элементов:
2100, 23, 40, 24, 2, 1.
Будем его сортировать. Раз легче сравнивать по два элемента, то разобьем поровну массив на два:
2150, 23, 40
и
24, 2, 1.
Получится по три элемента. Много! Разобьем поровну каждый массив, получится четыре массива:
2100, 23
40
24, 2
1
Отсортируем теперь каждый из массивов простым сравнением первого и второго элементов (там где они есть):
23, 2100
40
2, 24
1
И будем сливать обратно по предыдущему алгоритму – через буфер. После первого слияния получим два массива:
23, 40, 2100
1, 2, 24
И снова сливаем – уже в один массив:
1, 2, 23, 24, 40, 2100
Так мы отсортировали слиянием массив.
В сухом остатке
Таким образом, сортировка слиянием подразумевает разбиение массива поровну до тех пор пока из одного массива не получится несколько мелких — размером не более двух элементов. Два элемента легко сравнить между собой и упорядочить в зависимости от требования: по возрастанию или убыванию.
После разбиения следует обратное слияние, при котором в один момент времени (или за проход цикла) выбираются по одному элементу от каждого массива и сравниваются между собой. Наименьший (или наибольший) элемент отправляется в результирующий массив, оставшийся элемент остается актуальным для сравнения с элементом из другого массива на следующем шаге.
Выразим в коде (Java)
Пример сортировки по возрастанию двух отсортированных массивов:
int[] a1 = new int[] {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500};
int[] a2 = new int[] {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
int[] a3 = new int[a1.length + a2.length];
int i=0, j=0;
for (int k=0; k<a3.length; k++) {
if (i > a1.length-1) {
int a = a2[j];
a3[k] = a;
j++;
}
else if (j > a2.length-1) {
int a = a1[i];
a3[k] = a;
i++;
}
else if (a1[i] < a2[j]) {
int a = a1[i];
a3[k] = a;
i++;
}
else {
int b = a2[j];
a3[k] = b;
j++;
}
}
Здесь:
a1 и a2 – массивы, которые надо слить;
a3 – результирующий массив;
i и j – индексы для массивов a1 и a2 соответственно, которые указывают на текущие элементы на каждом шаге и образуют тот самый буфер.
Первые два условия проверяют, что бы индексы не вышли за переделы количества элементов в массивах. Третье и четвертое условия обеспечивают перемещение в массив наименьшего элемента из первого массива и из второго соответственно.
Функция сортировки слиянием
Оформим приведенный код как рекурсивную функцию, которая станет разделять массивы до тех пор, пока это возможно, с параметрами, соответствующими целому массиву при первом вызове, его половинам при втором и третьем вызовах и т. д.
private void SortUnsorted(int[] a, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
SortUnsorted(a, lo, mid);
SortUnsorted(a, mid + 1, hi);
int[] buf = Arrays.copyOf(a, a.length);
for (int k = lo; k <= hi; k++)
buf[k] = a[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = buf[j];
j++;
} else if (j > hi) {
a[k] = buf[i];
i++;
} else if (buf[j] < buf[i]) {
a[k] = buf[j];
j++;
} else {
a[k] = buf[i];
i++;
}
}
}
Здесь:
a – массив;
lo – позиция первого элемента в массиве (для первой итерации = 0);
hi – позиция последнего элемента в массиве (для первой итерации = a.length — 1).
Ссылки
Алгоритмы на Java
Cat's Cradle Quotes
Комментарии (11)
LoadRunner
15.04.2016 13:31+2Я не программист, но разве с самого начала не очевидно, что надо сравнивать первые элементы массивов, брать наименьший, сдвигать индекс на 1 и снова сравнивать? Без всяких буферов. Со стеками проще — там просто верхние элементы сравниваются.
А момент с разбиением массивов пополам напомнил qsort.
QtRoS
18.04.2016 18:00А момент с разбиением массивов пополам напомнил qsort.
Divide & Conquer же, неудивительно.
eandr_67
15.04.2016 14:00+6Типичный для новичка переусложнённый велосипед. Слияние двух отсортированных массивов производится простейшим кодом (вариант далеко не самый эффективный, но даже он будет работать быстрее, чем Ваш):
int i=0, j=0, k=0; while(i < a1.length && j < a2.length) { a3[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++]; } if(i< a1.length) { arraycopy(a1, i, a3, k, a1.length - i); } else if(j< a2.length) { arraycopy(a2, j, a3, k, a2.length - j); }
И кто Вам сказал такую глупость, что делить надо, пока не останется 2 элемента (а тем более, один)? Деление до минимального размера имеет смысл только для сортировки списков с последовательным доступом к элементам. Массивы же надо делить ровно до того момента, когда размер блока станет достаточно маленьким, чтобы применить эффективный алгоритм сортировки с прямым доступом к элементам. Да и само использование сортировки слиянием для массивов, полностью помещающихся а памяти — это демонстрация полного непонимания данного алгоритма в частности и полного же незнания даже минимальных основ теории алгоритмов в целом.
MiXei4
16.04.2016 06:41Сортировка слиянием — это не эффективный алгоритм сортировки? Почему его нельзя использовать для массивов?
eandr_67
16.04.2016 13:43+3Сортировка слиянием — очень эффективный алгоритм внешней сортировки. Разумеется, как любой алгоритм сложности O(n*ln(n)), он будет эффективен и для сортировки массивов… Но зачем, когда для массивов есть множество более эффективных алгоритмов внутренней сортировки?
Надо понимать, что для разных данных надо использовать разные алгоритмы.
Для массива из 10 чисел простейший, но имеющий минимальные накладные расходы, алгоритм сложности O(n^2) будет эффективнее, чем быстрый алгоритм сложности O(n*ln(n)): чем меньше объём данных, тем заметнее накладные расходы, требуемые для быстрых алгоритмов.
Для массива из 10 тысяч строк уже понадобится алгоритм сложности O(n*ln(n)). Но опять же, выбор алгоритма зависит от сортируемых данных и наличия ресурсов. Например, пирамидальная сортировка в среднем медленнее, чем быстрая, но если требуется минимизировать затраты памяти (например, в микроконтроллере), то эффективнее будет именно пирамидальная. А уж сортировка слиянием в задачах, требующих минимизации памяти, вообще не рассматривается.
А для линейного однонаправленного списка, или для файла, размер которого превышает объём RAM (вполне себе типичная ситуация для баз данных), будет использован один из алгоритмов внешней сортировки. В том числе и сортировка слиянием.
vidyacat
15.04.2016 14:32+2на пальцах сортировка слиянием отлично описана в википедии, в виде гифки.
в данной же статье я потерял мысль на фтором параграфе.
MaximChistov
15.04.2016 14:54Ваше «начали за здравие» это вообще не слияние, а простое запихивание элементов по очереди.
Правильное слияние:
Шаг 1.
Взять по элементу из обоих массивов.
Шаг 2.
Поместить больший элемент в результирующий массив
Шаг 3.
Попытаться взять следующий элемент из того массива, из которого мы на Шаге 2 поместили элемент в результирующий массив.
Еще остались элементы? Перейти к Шагу 2
Элементы закончились? Добавить все оставшиеся элементы второго массива(где они еще есть) в конец результирующего.
Шаг 4.
Конец
Aivendil
15.04.2016 15:17+5Мне сложно представить более сложный способ объяснить сортировку слиянием, чем тот, что использовался в статье:) Однако, не могу не отметить, что статья из песочницы. Человек пробует публиковать свои мысли и это прекрасно. Редко у кого первая статья бывает шедевром по содержанию. Всё приходит с опытом.
Автор молодец, что всё аккуратно оформил. Успехов в изучении програмирования!
gena_glot
15.04.2016 23:00Написал тотже самый код. У меня через по-другому.
1. Нам потребуется процедура copyArray(sourceArray, sourceStartPosition, destinationArray, destinationStartPosition) — замечу что копирование происходит фрагмента [sourceStartPosition; sourceArray.length — 1] в позиции [destinationStart; destinationStart + lengthOfSourceFragment — 1].
2. Код процедуры слияния
narray, murray — входные массейвы
rarray — выходной
narray — 0..n-1, length = n, i — indexer
murray — 0..m-1, length = m, k — indexer
rarray — 0..n+m-1, length = n+m, l — indexer
i, k, l = 0;
while ( i < n or k < m) {
x = narray[i];
y = murray[k];
if (x <= y) {
rarray[l] = x;
i++;
}
else {
rarray[l] = y;
k++;
}
l++;
}
if i = n-1 then copyArray(murray, k, rarray, l+1)
if k = m-1 then copyArray(narray, i, rarray, l+1)
vdem
Мягко говоря, данное описание сортировки слиянием воспринимается гораздо хуже, чем «академическое».