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