Сортировка слиянием — это алгоритм, используемый для сортировки списков. Он разбивает список на списки длиной 1, а затем объединяет их.
При их объединении каждый из массивов уже предварительно отсортирован. Итак, давайте сначала узнаем, как соединить два предварительно отсортированных массива.
Это помогает думать об этом вне области кода. Допустим, у вас есть две группы людей, обе расположены от самых низких до самых высоких. Если бы вы хотели объединить их в одну отсортированную группу, как бы вы это сделали?
Ответ проще, чем вы думаете. Допустим, группы упорядочены от самой низкой к самой высокой, и новую группу также нужно расположить от самой низкой к самой высокой.
Самый низкий человек должен быть первым человеком в одной из двух линий. Если два человека являются самыми низкими в своих группах, то тот из них, кто ниже ростом, является самым низким человеком в целом (или ничья).
Итак, мы тянем первого человека в обеих двух линиях. Мы выстраиваем их спиной к спине, а затем более короткая из двух входит в новую группу. Затем мы повторяем процесс, говоря самому низкорослому оставшемуся человеку добраться до конца новой группы, где он безраздельно правит как самый высокий человек, хотя бы на мгновение.
После того, как мы повторили процесс достаточно, чтобы одна из групп стала пустой, должна остаться одна группа с людьми в ней. Группа с людьми в ней остается в порядке и становится в конец новой группы.
Точно так же у вас есть единственная отсортированная группа. Помните об этом процессе, когда мы делаем это с кодом.
У вас есть два отсортированных массива.
arrA = [0,1,3,4,4,5,7,10,13,14,16,17,18,19,21,24,25,27,28,30]; arrB = [1,2,3,5,7,8,10,11,12,13,15,18,22,22,23,25,28,28,29,29];
Затем появляется новый отсортированный массив.
sorted = []
Первый элемент этих массивов должен быть наименьшим элементом. Тот из них, который наименьший, удаляется из своего массива и присоединяется к новому массиву.
if (arrA[0] < arrB[0]): sorted.append(arrA[0]) del arrA[0] else: sorted.append(arrB[0]) del arrB[0]
Этот процесс повторяется до тех пор, пока один из массивов не станет пустым. Мы можем воспроизвести этот процесс с помощью цикла while.
while (len(arrA) and len(arrB)):
Процесс выбора первого элемента каждого массива повторяется в цикле.
while (len(arrA) and len(arrB)): if (arrA[0] < arrB[0]): sorted.append(arrA[0]) del arrA[0] else: sorted.append(arrB[0]) del arrB[0]
Этот цикл завершит выполнение, как только одна из групп станет пустой. Чтобы завершить процесс здесь, мы могли бы выяснить, какой массив пуст, и переместить все в этом массиве в конец одного отсортированного массива.
Более простое решение — просто объединить ArrA и ArrB в конце singleSorted. JS просто ничего не добавит к пустому массиву, и решение будет в порядке.
return sorted + arrA + arrB
Теперь мы просто обернем это в функцию и получим полное решение.
def merge(arrA,arrB): sorted = [] while (len(arrA) and len(arrB)): if (arrA[0] < arrB[0]): sorted.append(arrA[0]) del arrA[0] else: sorted.append(arrB[0]) del arrB[0] return sorted + arrA + arrB
И если мы запустим функцию с нашими двумя массивами, мы получим это.
arrA = [0,1,3,4,4,5,7,10,13,14,16,17,18,19,21,24,25,27,28,30]; arrB = [1,2,3,5,7,8,10,11,12,13,15,18,22,22,23,25,28,28,29,29]; print(merge(arrA,arrB)); /* [0, 1, 1, 2, 3, 3, 4, 4, 5, 5, 7, 7, 8, 10, 10, 11, 12, 13, 13, 14, 15, 16, 17, 18, 18, 19, 21, 22, 22, 23, 24, 25, 25, 27, 28, 28, 28, 29, 29, 30] */
На всякий случай, если вы не поняли, вот видео на YouTube, объясняющее процесс. (Это JavaScript, но синтаксис — это единственное, что вам нужно c)
Итак, давайте сделаем следующий шаг. Мы собираемся разбить массив на части длиной в единицу, а затем соединить их вместе, используя этот алгоритм и рекурсию.
Давайте объявим функцию, которая это делает.
def mergeSort(arr):
Первое, что мы хотим сделать, это проверить, равна ли длина массива единице. Посмотрите на приведенный выше пример. Мы просто возвращаем массив, если его длина равна единице, потому что если есть только один элемент, он должен быть упорядочен.
if (len(arr) <= 1): return arr
Если массив не имеет длины, равной единице, мы хотим разделить его пополам и вызвать одну и ту же функцию для каждого из вновь сформированных массивов. Этот процесс известен как рекурсия.
pointer = int(len(arr) / 2) left = mergeSort(arr[0:pointer]) right = mergeSort(arr[pointer:len(arr)])
После этого мы хотим взять два массива, которые мы получили, и объединить их в один отсортированный массив. Эти массивы будут предварительно отсортированы, поэтому мы можем использовать функцию «слияния», которую мы создали выше.
return merge(left,right)
Вот как будет выглядеть окончательный код:
def merge(arrA,arrB): sorted = [] while (len(arrA) and len(arrB)): if (arrA[0] < arrB[0]): sorted.append(arrA[0]) del arrA[0] else: sorted.append(arrB[0]) del arrB[0] return sorted + arrA + arrB def mergeSort(arr): if (len(arr) <= 1): return arr pointer = int(len(arr) / 2) left = mergeSort(arr[0:pointer]) right = mergeSort(arr[pointer:len(arr)]) return merge(left,right)
Я добавил несколько операторов печати, чтобы помочь визуализировать процесс.
[52] [26] [26, 52] [93] [17] [17, 93] [17, 26, 52, 93] [77] [31] [31, 77] [44] [55] [20] [20, 55] [20, 44, 55] [20, 31, 44, 55, 77] [17, 20, 26, 31, 44, 52, 55, 77, 93] [17, 20, 26, 31, 44, 52, 55, 77, 93]
Каждое подмножество разбивается пополам, пока его длина не станет равной единице. Затем он сортируется слиянием с другим массивом с длиной, равной единице. Этот новый массив имеет длину два, но он отсортирован, поэтому мы можем вызвать для него «слияние» при присоединении к другому массиву.
