В прошлый раз мы рассмотрели использование рекурсии на примере возведения в степень. В этот раз мы применим рекурсию для создания алгоритма сортировки слиянием.
В сети легко найти множество вариаций решения данной задачи. Код, который мы рассмотрим в этой статье, будет написан так, чтобы быть максимально простым для понимания начинающих разработчиков.
Освежим в памяти суть сортировки слиянием:
Изначальный массив делится пополам до тех пор, пока длина "половинок" не станет равна 1. Это - базовый случай. Затем элементы двух "половинок" сравниваются и заносятся в результирующий массив в порядке возрастания.
Поскольку мы сначала делим массив, а затем собираем обратно, удобнее будет вынести эти операции в отдельные методы. Будем последовательны и начнем с деления. Раз мы хотим делить массив пополам до тех пор, пока длина "половинок" не станет равна 1, будет удобно использовать рекурсию.
Вначале опишем базовый случай:
public static int[] mergeSort(int[] src) {
if (src.length <= 1) {
return src;
}
}Затем "поделим исходный массив пополам". Это значит, что нам нужно создать два новых массива. Каждый возьмет половину элементов из исходного (src). Для простоты назовем их left и right. Применим метод Arrays.copyOfRange, в котором укажем по порядку:
Массив-источник, откуда будем копировать значения (src)
Индекс источника, с которого начнем (0)
Индекс источника, по достижению которого копирование прекратится* (src.length / 2)
int[] left = Arrays.copyOfRange(src, 0, src.length / 2);* Размер left будет равен промежутку от индекса 0 включительно до индекса src.length / 2 исключительно.
Аналогично поступим для right. В качестве первого индекса для копирования возьмем тот, на котором остановилось копирование в массив left, (по сути, это будет его длина), и пройдем до конца массива-источника:
int[] right = Arrays.copyOfRange(src, left.length, src.length);В итоге получим код:
public static int[] mergeSort(int[] src) {
if (src.length <= 1) {
return src;
}
int[] left = Arrays.copyOfRange(src, 0, src.length / 2);
int[] right = Arrays.copyOfRange(src, left.length, src.length);
}Осталось применить рекурсию - и метод будет "делить пополам" до тех пор, пока размер массива не станет равен 1.
Но перед этим давайте напишем второй метод, в котором мы опишем логику слияния. Суть его работы будет заключаться в том, что мы создадим новый массив result, в который будем помещать элементы массивов left и right по возрастанию. Помимо массива result, нам потребуется объявить переменные, которые выступят в роли счетчика для индекса каждого из массивов:
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int resIn = 0, leftIn = 0, rightIn = 0;Важно понять: поскольку мы начинаем объединение только после достижения базового случая (когда размеры массивов left и right равны 1), изначально мы сравниваем, по сути, просто два числа. Записывая их в порядке возрастания в результирующий массив размером 2, мы получаем маленький, но уже отсортированный массив. ��огично, что нам достаточно написать код, который объединяет по возрастанию элементы именно отсортированных массивов. Нам не требуется сравнивать каждый элемент с каждым! Вот почему сортировка слиянием О(n*log2(n)) быстрее сортировки путем сравнения каждого с каждым О(nn).
Итак, нам достаточно сравнить первые элементы двух массивов. Меньший будет добавлен в результирующий массив. Больший - пойдет на сравнение со следующим элементом соседа:
Напишем код. Поскольку массивы left и right могут быть разного размера, мы будем записывать значения в result, пока не дойдем до конца хотя бы одного из них:
while (indexL < left.length && indexR < right.length) {
result[index++] = left[indexL] < right[indexR] ? left[indexL++] : right[indexR++];
}Если в цикле выше мы дошли до конца одного массива, но не дошли до конца второго, то оставшиеся элементы также потребуется добавить к результирующему массиву:
while (index < result.length) {
result[index++] = indexL != left.length ? left[indexL++] : right[indexR++];
}Осталось только вернуть result. Код метода целиком:
private static int[] merge(int[] left, int[] right) {
int index = 0, indexL = 0, indexR = 0;
int[] result = new int[left.length + right.length];
while (indexL < left.length && indexR < right.length) {
result[index++] = left[indexL] < right[indexR] ? left[indexL++] : right[indexR++];
}
while (index < result.length) {
result[index++] = indexL != left.length ? left[indexL++] : right[indexR++];
}
return result;
}Итак, наши методы готовы. Остался последний штрих - добавление рекурсии:
public static int[] mergeSort(int... src) {
if (src.length <= 1) {
return src;
}
int[] left = Arrays.copyOfRange(src, 0, src.length / 2);
int[] right = Arrays.copyOfRange(src, left.length, src.length);
return merge(mergeSort(left), mergeSort(right));
}Теперь метод mergeSort, который делит массив на две половины, сам будет запрашивать результат их слияния. А слияние начнется только после того, как left и right достигнут базового случая, так как мы обращаемся к ним через тот же самый mergeSort. И вот, когда базовый случай достигнут, метод merge начнет сборку, а метод mergeSort - отправлять результат в merge, который был вызван предшествующей итерацией. В конце концов, мы дойдем до самого начала рекурсии и получим ответ.
Весь код целиком:
public static int[] mergeSort(int... src) {
if (src.length <= 1) {
return src;
}
int[] left = Arrays.copyOfRange(src, 0, src.length / 2);
int[] right = Arrays.copyOfRange(src, left.length, src.length);
return merge(mergeSort(left), mergeSort(right));
}
private static int[] merge(int[] left, int[] right) {
int index = 0, indexL = 0, indexR = 0;
int[] result = new int[left.length + right.length];
while (indexL < left.length && indexR < right.length) {
result[index++] = left[indexL] < right[indexR] ? left[indexL++] : right[indexR++];
}
while (index < result.length) {
result[index++] = indexL != left.length ? left[indexL++] : right[indexR++];
}
return result;
}Бонус: метод merge можно записать в короткой форме, чуть более сложной для восприятия:
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int i = 0, l = 0, r = 0; i < result.length; i++)
result[i] = l < left.length
&& (r == right.length || left[l] < right[r])
? left[l++] : right[r++];
return result;
}