Перевод статьи «Recursion and the Call Stack Explained By Reading A Book».
Сортировка слиянием это популярный алгоритм сортировки элементов массива от меньшего к большему. Ее часто сравнивают с сортировкой выбором, вставкой, пузырьковой сортировкой и многими другими.
Но когда я попробовал поискать в интернете простое объяснение работы сортировки слиянием, мне так и не удалось найти подходящее (очень простое) руководство.
Конечно, есть отличная визуализация от VisuAlgo, а на FreeCodeCamp есть доступное текстовое пояснение.
Но, несмотря на наличие этих материалов, мне все равно случалось подолгу вглядываться в блоки кода и думать, что же происходит на отдельно взятой строчке.
Так вот. В этом гайде вы найдете невероятно простое объяснение тог, как работает сортировка слиянием. Я объясню ее на примере серии теннисных турниров.
Чтобы разобраться в пояснениях, вам понадобится базовое понимание рекурсии. Приступим!
Основы сортировки слиянием
Одна из фундаментальных идей сортировки слиянием, как и всех остальных базовых алгоритмов JavaScript, состоит в том, что массив можно отсортировать только путем сравнения элементов попарно и нахождения большего из них.
Значит, нам нужно найти способ производить эти сравнения пар как можно эффективнее.
Давайте представим, что у нас есть массив из 8 чисел, которые мы должны отсортировать от меньшего к большему.
[4,6,7,2,1,10,9,3]
Только давайте будем представлять их в виде не просто чисел, а в виде уровней навыков теннисистов, по шкале от 1 до 10. Наша задача — определить, кто из игроков является лучшим в группе.
Используя сортировку слиянием, нам нужно рассортировать игроков, «построив» их по возрастанию уровня навыков. Это можно сделать при помощи серии теннисных матчей и определения победителя в каждом из них.
Но на настоящих теннисных соревнованиях игрокам не приходится пересекать всю страну, чтобы сразиться на одном огромном турнире. Вместо этого они соревнуются на более мелких турнирах, победители которых смогут сразиться за приз на национальном чемпионате.
Давайте представим, что мы ищем лучшего игрока-любителя в США.
Мы можем разделить всех игроков по часовым поясам: West (Тихоокеанское время), Mountain (Североамериканское горное время), Central (Североамериканское центральное время) и East (Североамериканское восточное время). Выглядеть это будет так:
Элементы с индексами 0 и 1, помеченные фиолетовым цветом, будут относиться к региону West и т. д.
Мы проведем 4 региональных состязания, а затем региональные победители сразятся за титул национального чемпиона.
То есть, мы будем последовательно находить «лучшего» из двух теннисистов, пока не дойдем до национального уровня. Лучший игрок на национальном уровне и будет лучшим в США!
Алгоритм сортировки слиянием
Я решил, что игроков будет именно 8, потому что так будет легче показать принцип работы алгоритма в статье.
Правильно работающий алгоритм должен уметь обрабатывать все массивы, в каждом из которых будет как минимум два элемента.
Также он должен справляться со случаями, когда в массиве нечетное число элементов, например, 9.
Наша сортировка слиянием состоит из двух основных частей:
- Разделение массива всех теннисистов на региональные турниры.
- Проведение теннисных матчей между победителями на высшем уровне, пока мы не сможем определить национального чемпиона.
Но нам нужна рекурсия, потому что, не зная размеров массива, мы понятия не имеем, сколько матчей придется провести. Наш алгоритм должен суметь справиться и с 8 теннисистами, и с 350.
Но рекурсией мы займемся позже. Сейчас давайте сфокусируемся на второй части — на соревнованиях, которые позволят нам сравнивать игроков попарно и рассортировывать их по уровню навыков. Мы будем исходить из того, что всегда побеждает лучший игрок.
Эта функция может запускаться неограниченное число раз, в зависимости от размера пула игроков.
Функция должна принимать два массива и комбинировать их в один, правильно отсортированный массив, где элементы будут располагаться от меньшего к большему. Делаться это будет в ходе поединков.
Вот как это выглядит для двух отсортированных массивов, каждый из которых содержит два элемента. Скажем, это турнир, проходящий после региональных.
Вот пара главных замечаний относительно этой GIF-ки:
- Мы можем перемещать только одного игрока за раз. Это потому, что игроков можно сравнивать только попарно. Мы не можем определить абсолютную позицию нескольких игроков сразу.
- Одна из сливаемых частей массива может содержать всех самых лучших игроков. Нам нужно, чтобы алгоритм справлялся со случаями, когда игроки остаются только на одной стороне.
Вот как выглядит код:
const tournament = (left, right) => {
var rankings = [];
while(left.length || right.length) {
if(left.length && right.length) {
if(left[0] < right[0]) {
rankings.push(left.shift())
} else {
rankings.push(right.shift())
}
} else if(left.length) {
rankings.push(left.shift())
} else {
rankings.push(right.shift())
}
}
return result;
}
Сразу кажется, что тут много всего, но вот главное:
- Строка 3: Мы начинаем перебирать игроков с обеих сторон квадратных скобок. Число итераций определяется длиной большего массива.
- Строки 4-10: Мы устраиваем «состязания» между первыми элементами каждого массива. Когда находим проигравшего, используем метод shift(), чтобы удалить игрока из турнира и добавить его в следующую ячейку отсортированного массива.
- Последняя строка: Мы возвращаем отсортированный массив, где игроки расставлены от худшего к лучшему.
Вот анимированная версия этого кода:
Ладно, давайте теперь вернемся к первой функции и посмотрим, как мы будем разбивать игроков по парам для соревнований на региональном уровне, а затем собирать их обратно для национального турнира.
Использование рекурсии в сортировке слиянием
Итак, у нас есть функция, позволяющая нам устраивать «состязания», но нам нужна также функция для разделения и сборки массива.
Прежде чем проводить какие-то соревнования, нам нужно разбить массив по «часовым поясам».
Вот как мы можем дойти от общего массива из 8 теннисистов разного уровня до четырех одиночных поединков:
Здесь мы видим 7 операций разделения массива на более мелкие массивы (или массив и одиночный элемент). Мы не можем жестко прописать это число, потому что если бы игроков было 16, то операций разделения было бы 15.
Напоминаю: в одиночных поединках мы можем определить только лучшего игрока из конкретной пары. Поэтому нам нужно разбивать массив аж до одиночных поединков, чтобы более мелкие массивы были правильно отсортированы, прежде чем будут сравниваться в дальнейшем.
А впоследствии нам нужно собрать массив обратно — после сортировки элементов на каждом уровне.
Вот как наш массив будет разбиваться на серии одиночных поединков:
И вот как он будет собираться обратно в отсортированном виде:
Вы заметили параллель между разделением и сборкой массива? Она подсказывает нам, что понадобится рекурсия.
Я сосредоточусь на «левой» части массива (или первой половине). Вот как мы можем построить стек вызовов, чтобы он позволил нам отсортировать массив:
При каждом разделении массива надвое мы добавляем вызов в стек вызовов, который ссылается на предыдущий вызов. В конце мы можем запустить функцию tournament() на каждом уровне, чтобы отсортировать каждый более маленький массив перед слиянием.
Вот как выглядит код:
const findWinner = (players) => {
if(players.length <= 1) return players;
const middle = players.length / 2 ;
const left = players.slice(0, middle);
const right = players.slice(middle, players.length);
return tournament(findWinner(left), findWinner(right));
}
let players = [4,6,7,2,1,10,9,3];
findWinner(players);
Строки 3-5 позволяют нам определить середину массива и разделить массив пополам. Делая это рекурсивно, мы сокращаем массив до размера 1 элемента.
Самый важный код у нас в строках 2 и 6.
В строке 2 мы обрабатываем случай, когда массив уменьшается до 1 элемента. Это говорит нам о том, что рекурсия должна остановиться, а мы можем запускать региональный турнир самого низкого уровня.
В строке 6 мы определяем, что в каждом вызове мы будем запускать функцию tournament() для отсортированного массива из предыдущего вызова (или одиночного состязания, если это самый низкий уровень).
Вот как это выглядит:
В этом примере мы доходим до уровня одиночных турниров в регионе «West» и «Mountain». Таким образом, мы можем начать с верхушки стека вызовов и к тому моменту, как мы дойдем до конца стека, мы найдем лучшего игрока. При этом мы будем многократно использовать функцию tournament().
