Это часть серии сообщений в блоге, в которых я обсуждаю алгоритмы сортировки JavaScript. Сначала я начал это путешествие с обсуждения пузырьковой сортировки и обнаружил, что хочу обсудить весь набор алгоритмов сортировки. В этом сообщении блога мы обсудим один из первых алгоритмов сортировки, который я начал изучать, - сортировку слиянием. Я слышал, как некоторые люди говорят, что это считается промежуточным алгоритмом сортировки, и я согласен, потому что шаги, предпринятые для реализации этого алгоритма. Я надеюсь, что это может быть хорошим справочником и напоминанием для тех, кто знаком с сортировкой слиянием. А для тех, кто плохо знаком с сортировкой слиянием, я надеюсь, что это можно будет использовать в качестве быстрого практического руководства.
Сортировка слиянием - это алгоритм, который работает рекурсивно. На этом остановимся и сразу перейдем к тому, что происходит при сортировке слиянием. Короче говоря, мы берем массив (несортированный) и разбиваем его на части, а затем объединяем их вместе, а затем выводим отсортированный массив. Это звучит как магия, а также как давно затянувшийся беспорядок в алгоритме, но в этом, казалось бы, безумном решении проблемы есть красота и порядок. Как это работает? Что ж, давайте разберемся по шагам.
Часть слияния, чтобы начать
Для начала давайте рассмотрим некоторые предварительные условия того, что необходимо для реализации сортировки слиянием. Сначала мы хотим начать с реализации функции, которая объединяет два отсортированных массива в качестве нашего помощника. Функция сделает это: она возьмет два массива (* Примечание: которые мы получим из нашего исходного несортированного массива), она просканирует оба массива и проверит каждый индекс, вставляя меньшее значение в новый массив. После того, как мы перебрали все значения и поместили их в новый массив, мы вернем этот новый и теперь отсортированный массив. Давайте создадим эту функцию.
function merge(array1, array2) {
//results is an empty array
let results = [];
let i = 0
let j = 0
while( i < array1.length && j < array2.length){
// We will compare the indexed items in each array, pushing the lower values into results. In the event that one of the arrays is larger, we create a while loop that says while either i or j is less then array1 or array2 respectively, we will continue pushing their elements and incrementing the value of i or j.
if(array2[j] > array1[i]){
results.push(array1[i])
i++
} else {
results.push(array2[j])
j++
}
while(i < array1.length) {
results.push(array1[i])
i++
}
while(j < array2.length) {
results.push(array2[j])
j++
}
}
return results;
}
Давайте разберем приведенный выше код. Мы создаем функцию под названием merge, которая принимает два аргумента: array1 и array2. В нем мы:
- Объявление трех переменных:
1) результаты, представляющие собой пустой массив,
2) i, которые представляют индекс массива1, и мы устанавливают его начальное значение на 0 и
3) j, который представляет индекс array2 и также имеет начальное значение 0.
- Затем мы создаем цикл, в котором говорится, что пока i и j меньше длины array1 и array2 соответственно, мы будем выполнять следующие условия:
- Пока мы поместили все значения из array1 и array2, сравниваем элементы array1 и array2, так что если array1 [i] меньше, чем array2 [j], или наоборот, мы поместим меньшее значение в массив результатов.
- В последних двух условиях while, если мы исчерпаем один массив перед другим, пока i или j меньше их соответствующей длины массива, мы продолжим проталкивать оставшиеся элементы массива, который все еще содержит элементы, в массив результатов.
- Затем мы вернем результаты, иначе говоря, отсортированный массив.
merge ([1, 50], [2, 8, 100])
// results = [], j = 0, i = 0
[1, 50] [2, 8, 100]
// arr2[j] > arr1[i] // 2 > 1 ? TRUE
// results = [ 1 ], j = 0, i = 1
// arr2[j] > arr1[i] // 2 > 50 ? FALSE
// results = [ 1, 2 ], j = 1, i = 1
{repeats}
// arr2[j] > arr1[i] // 8 > 50 ? FALSE
// arr2[j] > arr1[i] // 100 > 50 ? TRUE
// j < arr2.length // 2 < arr2.length ? TRUE
// => results = [ 1, 2, 8, 50, 100 ]
Сортировочная часть финала
Пройдем по части сортировки для сортировки слиянием. Сортировочная часть алгоритма будет работать рекурсивно. Помните, что мы начинаем с одного несортированного массива. Чтобы получить желаемый результат, этот алгоритм работает, разбивая наш массив на маленькие части. Проще говоря, мы хотим создать отдельные массивы для каждого элемента во всем нашем массиве, прежде чем собирать его обратно. Вам может быть интересно, где в этом смысл.
Давайте подумаем об этом так:
Представьте, что вы начали с массива из восьми несортированных элементов.
[3, 1, 6, 5, 2, 8, 7, 4] (без сортировки)
Давайте разделим массив на два так, чтобы теперь у нас было два массива по четыре несортированных значения.
[3, 1, 6, 5] [2, 8, 7, 4] (несортировано)
А затем повторите это снова.
Итак, теперь у нас есть четыре несортированных массива с двумя значениями…
[3, 1] [6, 5] [2, 8] [7, 4] (несортированный)
и затем, наконец, восемь массивов по одному значению в каждом.
[3] [1] [6] [5] [2] [8] [7] [4] (отсортировано) »
Преимущество разбиения несортированного массива на несколько массивов с одним отдельным элементом заключается в том, что, когда в массиве только один элемент, этот массив уже отсортирован, что упрощает объединение и, в конечном итоге, сортировку наших массивов. Кроме того, для сортировки массива требуется гораздо меньше шагов, хотя написанный код выглядит так, как будто он делает намного больше, чем наши предыдущие алгоритмы сортировки. По правде говоря, алгоритм работает в большом количестве n * log n, и это здорово. В нашем примере с несортированным массивом у нас есть 8 элементов в массиве, который представляет n. Разбивая массив, мы реализуем логику двоичного типа, то есть противоположность возведению значения в квадрат. Другими словами, сколько раз можно уменьшить вдвое массив с восемью числами, прежде чем мы дойдем до одного элемента на массив. 8 делится пополам в 3 раза, прежде чем станет 1.
8/2 = ›4/2 =› 2/2 = ›1
Чтобы реализовать сортировку с помощью слияния
Опять же, мы хотим разделить наш массив на две половины, пока у нас не будут пустые массивы или один элемент с array.slice. Мы хотим сделать это, реализовав рекурсию, чтобы мы разрезали наш массив на «имущие» до тех пор, пока у нас не получится больше. А затем, когда мы достигли нашего базового случая, то есть точки, когда мы больше не можем разрезать, потому что значения каждого индекса равны 0 или 1, мы начнем объединять массивы и сортировать их одновременно с нашей функцией слияния.
function mergeSort(array){
if(array.length <= 1) return array;
let midPoint = Math.floor(array.length/2)
let left = mergeSort(array.slice(0, mid));
let right = mergeSort(array.slice(mid));
return merge(left, right);
}
Окончательный разрыв.
В приведенном выше коде мы разбиваем наш массив пополам. Мы начинаем с оператора catch, согласно которому, если длина нашего массива меньше или равна единице, мы вернем массив. Это будет основой, когда мы больше не сможем разрезать массив, потому что его длина равна 0 или 1.
Во второй строке мы создаем переменную с именем midPoint, которая равна половине значения длины наш массив. Math.floor обеспечивает округление до ближайшего целого числа. Итак, если мы разделим 9 на 2, даже если технически значение будет равно 4,5, мы округлим его до 4.
В следующих строках мы создаем переменные «left» и «right» и делаем рекурсивный вызов для mergeSort, где мы передаем в качестве аргументов левую и правую половину исходного массива. Здесь мы создаем стек вызовов рекурсивных функций, которые при выполнении перейдут к последней строке нашей функции mergeSort, которая будет побитно возвращать отсортированный массив, что в конечном итоге приведет к возврату нашего окончательного отсортированного массива.
Еще раз повторюсь, сортировка слиянием работает, разбивая массив на более мелкие массивы из 0 или 1 элемента, а затем создавая недавно отсортированный массив. Подход «разделяй и властвуй». Рекурсивное разделение массивов до тех пор, пока у нас не будет единичных подмассивов, это гарантирует, что массивы одиночных элементов будут отсортированы, а затем могут быть снова объединены вместе.
[3, 1, 6, 5, 2, 8, 7, 4] (без сортировки)
[3, 1, 6, 5,] [2, 8, 7, 4] (без сортировки)
[3, 1] [6, 5] [2, 8] [7, 4] (несортировано)
[3] [1] [6] [5] [2] [8] [7] [4] ] (отсортировано 0 индексных массивов)
[1, 3] [5, 6] [2, 8] [4, 7] (отсортированные массивы)
[1, 3, 5, 6] [2 , 4, 7, 8] (отсортированные массивы)
[1, 2, 3, 4, 5, 6, 7, 8] (отсортированный массив)
