Сортировка слиянием в Java
В этом руководстве мы рассмотрим алгоритм сортировки слиянием и его реализацию в Java .
Сортировка слиянием — один из наиболее эффективных методов сортировки, основанный на парадигме «разделяй и властвуй» .
2. Алгоритм
Сортировка слиянием — это алгоритм «разделяй и властвуй», в котором мы сначала делим проблему на подзадачи. Когда решения для подзадач готовы, мы объединяем их вместе, чтобы получить окончательное решение проблемы.
Мы можем легко реализовать этот алгоритм с помощью рекурсии, так как мы имеем дело с подзадачами, а не с основной проблемой.
Мы можем описать алгоритм как следующий двухэтапный процесс:
- Разделить: на этом шаге мы делим входной массив на 2 половины , причем точка опоры является средней точкой массива. Этот шаг выполняется рекурсивно для всех полумассивов до тех пор, пока не останется разделяемых полумассивов.
- Conquer: на этом этапе мы сортируем и объединяем разделенные массивы снизу вверх и получаем отсортированный массив.
На следующей диаграмме показан полный процесс сортировки слиянием для примера массива .
Если мы внимательно посмотрим на диаграмму, то увидим, что массив рекурсивно делится на две половины, пока размер не станет равным 1. Как только размер станет равным 1, в действие вступают процессы слияния, которые начинают объединять массивы обратно при сортировке:
3. Реализация
Для реализации мы напишем функцию mergeSort , которая принимает входной массив и его длину в качестве параметров. Это будет рекурсивная функция, поэтому нам нужна база и рекурсивные условия.
Базовое условие проверяет, равна ли длина массива 1, и оно просто возвращается. В остальных случаях будет выполнен рекурсивный вызов.
Для рекурсивного случая мы получаем средний индекс и создаем два временных массива, l[] и r[] . Затем мы рекурсивно вызываем функцию mergeSort для обоих подмассивов:
public static void mergeSort(int[] a, int n) if (n 2) return; > int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i mid; i++) l[i] = a[i]; > for (int i = mid; i n; i++) r[i - mid] = a[i]; > mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); > Затем мы вызываем функцию слияния , которая принимает входные данные и оба подмассива, а также начальный и конечный индексы обоих подмассивов .
Функция слияния сравнивает элементы обоих подмассивов один за другим и помещает меньший элемент во входной массив.
Когда мы достигаем конца одного из подмассивов, остальные элементы из другого массива копируются во входной массив, тем самым давая нам окончательный отсортированный массив:
public static void merge( int[] a, int[] l, int[] r, int left, int right) int i = 0, j = 0, k = 0; while (i left && j right) if (l[i] r[j]) a[k++] = l[i++]; > else a[k++] = r[j++]; > > while (i left) a[k++] = l[i++]; > while (j right) a[k++] = r[j++]; > > Модульный тест для программы:
@Test public void positiveTest() int[] actual = 5, 1, 6, 2, 3, 4 >; int[] expected = 1, 2, 3, 4, 5, 6 >; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); > 4. Сложность
Поскольку сортировка слиянием является рекурсивным алгоритмом, временная сложность может быть выражена в виде следующего рекурсивного соотношения:
2T(n/2) соответствует времени, необходимому для сортировки подмассивов, а O(n) — времени для объединения всего массива.
При решении временная сложность составит O(nLogn).
Это верно для наихудшего, среднего и наилучшего случаев, поскольку он всегда будет делить массив на два, а затем объединять.
Объемная сложность алгоритма составляет O(n), так как мы создаем временные массивы при каждом рекурсивном вызове.
5. Вывод
В этой краткой статье мы рассмотрели алгоритм сортировки слиянием и то, как мы можем реализовать его в Java.
Весь рабочий код доступен на GitHub .
Сортировка слиянием по-простому
Допустим у нас есть два массива чисел, отсортированных по возрастанию.
int[] a1 = new int[] ; int[] a2 = new int[] ; Необходимо слить их в один упорядоченный массив.
int[] a3 = new int[a1.length + a2.length]; Это задача для сортировки слиянием.
Что это такое? В интернете есть ответ, есть описание алгоритма, но я его не понял с одного присеста и решил разобраться сам. Для этого необходимо понять базовый принцип алгоритма, чтобы можно было по памяти воссоздать алгоритм применительно к своей задаче.
Начали за здравие
Давайте пойдем постепенно и воспользуемся тем, что лежит на поверхности: будем брать поочередно по одному элементу из каждого массива, сравнивать их и «сливать» в один массив. Меньший элемент будем ставить первым, больший – вторым. Тогда после первого прохода все нормально:
А после второго прохода уже не очень:
Понятно, что надо сравнивать элементы еще и с уже добавленными.
Начнем еще раз
Пусть у нас будет некий временный буфер из сравниваемых на каждом шаге элементов. После первого прохода в него попадут 21 и 10. После сравнения мы переместим из буфера в результирующий массив меньший элемент 10 и оставим больший элемент 21, потому что не знаем, что будет за ним.
После второго прохода в буфере будет 21, 23 и 11. Что с ними делать – непонятно, сравнить более двух элементов можно, но уже не так просто.
Давайте тогда условимся, что будем брать в этот буфер по одному элементу от каждого массива. Так как проще сравнивать два элемента между собой, да и вообще у нас две сущности – два массива. Тогда после второго прохода в буфере будет 21 и 11, потому что «представитель» первого массива в буфере уже есть – это 21. Сравниваем их и меньший отправляем в результирующий массив. Тогда после второго прохода будем иметь в результирующем массиве:
На третьем проходе берем в буфер из второго массива 41, потому что «представитель» первого массива в буфере так и остался. Сравниваем 21 и 41, и наконец-то убираем из буфера 21.
После третьего прохода будем иметь в результирующем массиве:
На четвертом проходе будем сравнивать два значения из буфера — 41 и 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. То есть нужно для каждого индекса выполнять проверку – не превысили ли мы количество элементов в каждом из массивов.
Усложним задачу
А если у нас не отсортированные массивы? Обычно задача сводится к тому, чтобы отсортировать один массив. Тогда сортировка слиянием тоже может быть использована.
Пусть первый массив (для примера возьмем из него несколько элементов) имеет следующее расположение элементов:
Будем его сортировать. Раз легче сравнивать по два элемента, то разобьем поровну массив на два:
Получится по три элемента. Много! Разобьем поровну каждый массив, получится четыре массива:
Отсортируем теперь каждый из массивов простым сравнением первого и второго элементов (там где они есть):
И будем сливать обратно по предыдущему алгоритму – через буфер. После первого слияния получим два массива:
И снова сливаем – уже в один массив:
Так мы отсортировали слиянием массив.
В сухом остатке
Таким образом, сортировка слиянием подразумевает разбиение массива поровну до тех пор пока из одного массива не получится несколько мелких — размером не более двух элементов. Два элемента легко сравнить между собой и упорядочить в зависимости от требования: по возрастанию или убыванию.
После разбиения следует обратное слияние, при котором в один момент времени (или за проход цикла) выбираются по одному элементу от каждого массива и сравниваются между собой. Наименьший (или наибольший) элемент отправляется в результирующий массив, оставшийся элемент остается актуальным для сравнения с элементом из другого массива на следующем шаге.
Выразим в коде (Java)
Пример сортировки по возрастанию двух отсортированных массивов:
int[] a1 = new int[] ; int[] a2 = new int[] ; int[] a3 = new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k 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 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).