Кто-то сказал однажды, что
…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
ссылка на оригинал статьи https://habrahabr.ru/post/281675/
Добавить комментарий