В прошлый раз мы рассмотрели использование рекурсии на примере возведения в степень. В этот раз мы применим рекурсию для создания алгоритма сортировки слиянием.
В сети легко найти множество вариаций решения данной задачи. Код, который мы рассмотрим в этой статье, будет написан так, чтобы быть максимально простым для понимания начинающих разработчиков.
Освежим в памяти суть сортировки слиянием:
Изначальный массив делится пополам до тех пор, пока длина "половинок" не станет равна 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 (leftIn < left.length && rightIn < right.length)
if (left[leftIn] < right[rightIn])
result[resIn++] = left[leftIn++];
else result[resIn++] = right[rightIn++];
Если в цикле выше мы дошли до конца одного массива, но не дошли до конца второго, то оставшиеся элементы также потребуется добавить к результирующему массиву:
while (resIn < result.length)
if (leftIn != left.length)
result[resIn++] = left[leftIn++];
else result[resIn++] = right[rightIn++];
Осталось только вернуть result. Код метода целиком:
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int resIn = 0, leftIn = 0, rightIn = 0;
while (leftIn < left.length && rightIn < right.length)
if (left[leftIn] < right[rightIn])
result[resIn++] = left[leftIn++];
else result[resIn++] = right[rightIn++];
while (resIn < result.length)
if (leftIn != left.length)
result[resIn++] = left[leftIn++];
else result[resIn++] = right[rightIn++];
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 resIn = 0, leftIn = 0, rightIn = 0;
int[] result = new int[left.length + right.length];
while (leftIn < left.length && rightIn < right.length)
if (left[leftIn] < right[rightIn])
result[resIn++] = left[leftIn++];
else result[resIn++] = right[rightIn++];
while (resIn < result.length)
if (leftIn != left.length)
result[resIn++] = left[leftIn++];
else result[resIn++] = right[rightIn++];
return result;
}
Бонус: метод merge можно записать в короткой форме, чуть более сложной для восприятия:
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int k = 0, i = 0, j = 0; k < result.length; k++)
result[k] = i < left.length && (j == right.length || left[i] < right[j]) ? left[i++] : right[j++];
return result;
}
Комментарии (15)
Sergey_zx
15.01.2023 02:17А зачем тут вообще память то выделять?
Меняем объекты списка сначала в парах, потом в четверках, и. т д. И лучше в цикле, а не рекурсией, ибо рекурсия и стек жрет, и время на вызовы-возвраты.
Если хочется ускорить процесс, то создаем буфер и индексами, или указателями на обьекты и сортируем его. Тогда экономим время на многократном свапе объектов.
yeputons
15.01.2023 04:58В парах можно. А вот в четвёрках и дальше у вас поменять уже без дополнительной памяти не получится. Там может оказаться надо переместить 2/3 правого массива в начало, а левый и оставшуюся 1/3 правого склеить вперемешку. Тогда непонятно, куда деть первые 2/3 левого массива так, чтобы это было быстро, не рушило порядок элементов в нём, и элементы можно было отличить от оставшихся элементов правого массива.
Sergey_zx
15.01.2023 05:40Да, я ошибся. Простым способом попарным обменом не обойтись. Нужен еще буфер размером с исходный.
nagayev
15.01.2023 21:36левая половина от 0 до длина/2
А если длина будет нечетным числом?
Полагаю тут забыли округлить.
remindscope Автор
16.01.2023 04:46Выражение длина/2 округлится автоматически в меньшую сторону, поскольку на вход в метод подаётся тип данных int, который представляет собой целочисленное значение. Размер массива, как и индексы его элементов, не могут быть дробными.
Zara6502
16.01.2023 10:23делал такую сортировку без рекурсии и буфера, по скорости страдает конечно, так как много проверок, но памяти требуется только sizeof(src[x]) для обмена.
а анимацию "Сортировка слиянием" вы сами делали или с просторов сети?
remindscope Автор
16.01.2023 13:23Да, обычным циклом будет экономнее. Я преследовал цель использовать рекурсию, поэтому без жертв не обошлось.
Гифки нашел в сети.
s_f1
Если я правильно понял, вы рекурсивно выделяете N памяти? Не надо так, особенно, с тегом новичкам. Переучиваться всегда сложнее.
aamonster
Кажется, это статья из цикла "сейчас я буду объяснять алгоритм, пока не пойму его".
ЗЫ: Выделяет, кажется, в общей сложности 2N (для вложенных уровней рекурсии массивы короче). Непривычно, обычно сортировки делают in-place (если это не махровая функциональщина)
s_f1
В том-то и дело, что N*lnN памяти. Линейно бы ещё куда ни шло, ведь классический merge тоже подразумевает копию массива.
aamonster
Да не, O(N). Прикиньте момент, когда рекурсия дошла до дна: на самом верхнем уровне (сортируем массив длиной N) выделено два массива по N/2, уровнем ниже (сортируем массив длиной N/2) два по N/4 и так далее. В сумме 2N.
Тут больше доставляет, что будет проделано O(N) выделений из кучи. Сама сортировка, мне кажется, за этим потеряется.
s_f1
aamonster
Вызовы для правой и левой части происходят последовательно. Т.е. к моменту возврата для одной из частей – вся её цепочка выделений (фу, гадость-то какая) уже схлопнется, память (кроме return value) может быть освобождена.
remindscope Автор
Спасибо за замечание. Полностью согласен с тем, что с точки зрения использования памяти данное решение неэффективно.