Возникли проблемы с пониманием того, сколько массивов фактически создается в алгоритме сортировки слиянием.

Я изучал алгоритм сортировки слиянием и не могу сделать вывод, сколько массивов фактически создается как часть алгоритма. В некоторой литературе говорится, что весь исходный массив копируется в новый отсортированный массив. Но это означает, что было создано только 2 массива.

Насколько я понимаю, алгоритм сортировки слиянием состоит из двух основных шагов. Разделение и слияние. Я думал, что если вы дадите сортировке слиянием массив из 100 слотов, он фактически создаст новые массивы, поскольку он разбивается посередине на 100 > 50/50 > 25/25 > 12/13 > 6/5 > 3/3 > 1/1. . После всех этих разбиений на данный момент у него в памяти 12 или 13 массивов. И затем, когда, наконец, он копирует все это в новые массивы из 1 > 2 > 3 или 4 > 6 > 12 > 25 > 50 > 100.

Это еще 8 массивов (грубо говоря).

Но в учебниках я читаю такие вещи:

Вы можете задаться вопросом, где в памяти расположены все эти подмассивы. В алгоритме создается массив рабочей области того же размера, что и исходный массив. Подмассивы хранятся в разделах массива рабочей области. Это означает, что подмассивы в исходном массиве копируются в соответствующие места в массиве рабочей области. После каждого слияния массив рабочей области копируется обратно в исходный массив.

-- Структуры данных и алгоритмы в Java Роберт Лафоре


sorting algorithm data-structures mergesort binary-search-tree
person Doublespeed    schedule 22.03.2016    source источник
comment
Вы можете реализовать сортировку слиянием на месте: stackoverflow.com/q/2571049/3788176. Или не. Таким образом, количество создаваемых массивов зависит от реализации.   -  person Andy Turner    schedule 22.03.2016
comment
Эти предоставленные комментарии не дают достаточно подробностей. Конечно, это зависит от реализации. Но допустим, что это не сортировка слиянием на месте (Rocket Science). Это базовая сортировка слиянием в CS101, тогда сколько массивов создается??   -  person Doublespeed    schedule 22.03.2016

Ответы (3)


arrow_upward
1
arrow_downward

Рассмотрим пару последних этапов типичной реализации сортировки слиянием. Нам нужно два массива - основной и вспомогательный, и объединить подмассивы из вспомогательного массива в основной.

перед некоторым этапом слияния (| обозначает начало каждой части массива (начальный индекс)) - мы объединяем подмассив A с подмассивом B, чтобы заполнить первую половину массива назначения, и объединяем подмассив C с подмассивом D, чтобы заполнить вторую половину массива назначения :

Auxiliary array:  |AAAA|BBBB|CCCC|DDDD
Main array:       ..................

после слияния (я использую произвольный порядок)

Auxiliary array:  ...............
Main array:       ABBABBAADCDDCCDC

после копирования, перед окончательным слиянием

Auxiliary array:  |ABBABBAA|DCDDCCDC
Main array:      ................
person MBo    schedule 22.03.2016
comment
Так это действительно только 2 массива? Я имею в виду рекурсивный подход к сортировке слиянием. То есть один и тот же массив передается рекурсивным вызовам или Merge-sort и Merge()? - person Doublespeed; 22.03.2016
comment
Да, всего 2 массива. Посмотрите на первый код здесь: en.wikipedia.org/wiki/Merge_sort#Top-down_implementation - массивы A и B (здесь целевой массив фазы слияния - вспомогательный B) - person MBo; 23.03.2016

arrow_upward
0
arrow_downward

Даже если вы «разделите» свой массив, вам не нужно создавать 2 новых массива. У вас всегда одинаковое количество слотов (здесь 100, даже если это 50*2 или 25*4...)

Вы просто перемещаете данные в правильное место в массиве (после первого разделения 50 первых слотов являются первым массивом, а 50 последних слотов - вторым массивом)

Вам не нужно хранить массивы, просто индексы того, где они начинаются в большом массиве.

person Fabich    schedule 22.03.2016

arrow_upward
0
arrow_downward

Учебник относится к достаточно эффективным реализациям слияния, когда выполняется однократное выделение массива рабочей области того же размера, что и оригинал. После этого все объединяемые подмассивы являются частями либо массива рабочей области, либо исходного массива, доступ к которым осуществляется через индексы (или указатели).

Сортировка слиянием сверху вниз использует рекурсию для создания динамического стека пар индексов для представления подмассивов. Сортировка слиянием снизу вверх пропускает рекурсию и использует итерацию для создания индексов, начиная с размера подмассива, равного 1.

person rcgldr    schedule 22.03.2016