Что такое сортировка слиянием?
mergeSort — это один из многих алгоритмов, используемых в компьютерных науках для того, чтобы взять коллекцию и упорядочить ее определенным образом. Этот пост будет идти шаг за шагом и объяснять, как при передаче набора данных функция mergeSort может рекурсивно вызывать себя, чтобы вернуть упорядоченный список.
Разбираем
Так как же работает mergeSort? Как и в случае с большинством алгоритмов сортировки, идея довольно проста: взять коллекцию и вернуть ее в определенном порядке. Помня о нашей теме сортировки слиянием, как эта концепция реализуется в коде?
Разделяй и властвуй
Представьте, что у вас есть банка с монетами, которые вы хотите рассортировать. Сколько различных способов у нас есть, чтобы организовать их? На самом деле довольно много. Учитывая, что мы знаем, что есть несколько способов сделать это, давайте продолжим, как если бы мы собирались сортировать эти монеты, реализуя технику mergeSort.
Если бы я засунул руку в банку с мелочью и бросил монеты на стол, я мог бы ожидать, что монеты будут в следующем порядке:
var coins = [ 25, 5, 10, 5, 1, 5, 10, 1 ]
Концептуально логика сортировки слиянием может показаться несколько абстрактной. В то время как алгоритмы типа bubbleSort рассматривают один элемент коллекции и сравнивают его с последующими элементами, mergeSort не отдает приоритет поиску каких-либо значений коллекции при ее первом вызове. Вместо этого mergeSort будет делить себя пополам снова и снова, пока каждое значение коллекции не будет содержаться в собственном уникальном массиве. Как только каждое значение в коллекции будет изолировано, коллекция будет постепенно перестраиваться путем слияния этих подмножеств упорядоченным образом.
Учитывая наш первоначальный набор мелочи, давайте посмотрим, как слияниеSort будет распределять наши монеты:
[ 25, 5, 10, 5, 1, 5, 10, 1 ] // divide the collection in half [ 25, 5, 10, 5], [ 1, 5, 10, 1] // divide the collection in half again [ 25, 5 ], [ 10, 5 ], [ 1, 5 ], [ 10, 1 ] // one more time... [ 25 ], [ 5 ] , [ 10 ], [ 5 ] , [ 1 ] , [ 5 ], [ 10 ] , [ 1 ]
Объединяем все вместе
Теперь, когда мы изолировали каждое отдельное значение, давайте посмотрим, как mergeSort организует их в упорядоченный список. Поскольку мы уже имеем дело с коллекцией отсортированных массивов (сортировка не является проблемой для массивов с одним значением), слияние коллекций на этом этапе становится относительно простым. Используя текущее состояние изменения кармана, перегруппировка отсортированных элементов обратно в единую коллекцию будет выглядеть примерно так:
[ 25 ], [ 5 ], [ 10 ], [ 5 ], [ 1 ], [ 5 ], [ 10 ], [ 1 ] // merge [ 5, 25 ], [ 5, 10 ], [ 1, 5 ], [ 1, 10 ] // merge again [ 5, 5, 10, 25 ], [ 1, 1, 5, 10 ] // one more time... [ 1, 1, 5, 5, 5, 10, 10, 25 ]
Как указывалось ранее, концепция любого алгоритма сортировки очень проста, и mergeSort не является исключением. Все, что мы пытаемся сделать, это переставить коллекцию в последовательном порядке. Однако объяснить логику сортировки слиянием гораздо сложнее, чем объяснить лежащую в ее основе концепцию. Давайте взглянем на код, чтобы пролить свет на то, как реализован алгоритм.
Как это работает
Сначала мы собираемся сосредоточиться на слиянии. Как только значения в коллекции были изолированы, мы должны затем снова объединить их в единую коллекцию. Здесь произойдет слияние. Это проще всего понять, сравнивая два массива с длиной, равной единице:
leftHalf = [6]
rightHalf = [4]
function merge(leftHalf, rightHalf) {
let sorted = []
while(leftHalf.length !== 0 && rightHalf.length !== 0) {
let lesserVal = leftHalf[0] < rightHalf[0] ?
leftHalf.shift() : rightHalf.shift()
sorted.push(lesserVal)
}
return sorted.concat(leftHalf).concat(rightHalf)
}
// merge([6], [4]) === [4, 6]
Эта функция принимает два массива и, хотя длина каждого массива равна единице или больше, сравнивает значение по первому индексу каждого из них. В этом случае мы сортируем от наименьшего к наибольшему, поэтому меньшее значение будет удалено из исходного массива и вставлено в новый массив. Этот процесс будет продолжаться до тех пор, пока любой из массивов не станет пустым, и он увидит новый массив, объединенный с двумя массивами, переданными в качестве аргументов.
Обратите внимание, что эта функция даст нам желаемый результат только в том случае, если мы имеем дело с двумя уже отсортированными массивами. Если бы мы передавали несортированные массивы в нашу функцию слияния, сравнение по-прежнему брало бы меньшее значение из исходного массива и перемещало его в новый массив, но мы все равно остались бы с окончательным массивом, значения которого не являются последовательными.
firstUnsorted = [3,5,1] secondUnsorted = [6,2,4] // merge(firstUnsorted, secondUnsorted) === [3, 5, 1, 6, 2, 4]
Как программисты, мы должны учитывать возможность того, что наша коллекция может быть не отсортирована. Как мы можем взять коллекцию и разделить ее на серию отсортированных массивов, как в примерах выше? Для этого шага нам нужно определить новую функцию, которая возьмет нашу коллекцию и разделит ее на отдельные элементы. Только после того, как элементы будут полностью разделены, мы начнем объединять значения коллекции.
function mergeSort(arr) {
let midpoint = arr.length / 2
let leftHalf = arr.slice(0, midpoint)
let rightHalf = (arr.slice(midpoint, arr.length))
if(arr.length < 2) {
return arr
} else {
return merge(mergeSort(leftHalf), mergeSort(rightHalf))
}
}
Как видите, наша функция mergeSort() служит двум целям. Во-первых, он берет текущий массив и делит его на две половины. Затем он проверяет, имеет ли исходный массив длину, равную 1. Если да, он возвращает массив (массив, содержащий один элемент). В противном случае он вызовет нашу функцию слияния, передав ей возвращаемое значение mergeSort(firstHalf) в качестве первого аргумента и mergeSort(secondHalf) в качестве второго аргумента.
Время выполнения сортировки слиянием
Время выполнения mergeSort считается «быстрым», поскольку количество времени, которое требуется для завершения, не прямо пропорционально размеру коллекции. Давайте используем нашу предыдущую коллекцию монет в качестве примера и попробуем разобрать ее.
var coins = [ 25, 5, 10, 5, 1, 5, 10, 1 ]
Чтобы разделить коллекцию на ряд индивидуально отсортированных массивов, нам пришлось бы сделать 3 деления:
[ 25, 5, 10, 5, 1, 5, 10, 1 ]
// divide one array in half
[ 25, 5, 10, 5 ] , [ 1, 5, 10, 1 ]
// divide two arrays in half
[ 25, 5 ] , [ 10, 5 ] , [ 1, 5 ] , [ 10, 1 ]
// divide four arrays in half
[ 25 ] , [ 5 ] , [ 10 ] , [ 5 ] , [ 1 ] , [ 5 ] , [ 10 ] , [ 1 ]После того, как деления были сделаны, потребуется 3 слияния, чтобы вернуть отсортированный массив целиком:
[ 25 ], [ 5 ], [ 10 ], [ 5 ], [ 1 ], [ 5 ], [ 10 ], [ 1 ] // merge one-element arrays to form arrays with a length of two [ 5, 25 ] , [ 5, 10 ] , [ 1, 5 ] , [ 10, 1 ] // merge two-element arrays to form arrays with a length of four [ 5, 5, 10, 25 ] , [ 1, 1, 5, 10 ] // merge four-element arrays to form an array with a length of eight [ 1, 1, 5, 5, 5, 10, 10, 25 ]
Как видите, чтобы перестроить коллекцию из 8 элементов, нам нужно сначала разделить ее пополам 3 раза (чтобы изолировать значение по каждому индексу), а затем сделать 3 слияния (чтобы объединить и отсортировать элементы ). Давайте посмотрим на массив длиной 16. Потребуется ли в два раза больше шагов?
[ 25, 5, 10, 5, 1, 5, 10, 1, 25, 5, 10, 5, 1, 5, 1, 1 ] // divide one array in half [ 25, 5, 10, 5, 1, 5, 10, 1 ], [25, 5, 10, 5, 1, 5, 1, 1 ] // divide two arrays in half [ 25, 5, 10, 5 ], [1, 5, 10, 1 ], [25, 5, 10, 5 ], [1, 5, 1, 1 ] // etc... [25, 5],[10, 5],[1, 5],[10, 1],[25, 5],[10, 5],[1, 5],[1, 1 ] // etc... [25],[5],[10],[5],[1],[5],[10],[1],[25],[5],[10],[5],[1],[5],[1],[1] // then to merge the arrays... // merge one-element arrays to form arrays with a length of two [5, 25], [5, 10], [1, 5], [1, 10], [5, 25], [5, 10], [1, 5] , [1, 1] // merge two-element arrays to form arrays with a length of four [5, 5, 10, 25] , [1, 1, 5, 10] , [5, 5, 10, 25] , [1, 1, 1, 5] // etc... [1, 1, 5, 5, 5, 10, 10, 25] , [1, 1, 1, 5, 5, 5, 10, 25] // etc... [1, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5, 10, 10, 10, 25, 25]
Сортировка коллекции по этой методике не займет вдвое больше времени. В этом примере нам нужно сделать только четыре деления и четыре слияния — всего на два шага больше, чем в предыдущем примере. Поскольку mergeSort позволяет быстрее разбивать нашу коллекцию на ряд отдельных частей, мы можем быстрее объединять эти части во время сортировки нашей коллекции.
