Mergesort, который сохраняет память

Question

Я беру урок по Алгоритмам, и последние домашние задания действительно ставят меня в тупик. По сути, назначение состоит в том, чтобы реализовать версию сортировки слиянием, которая не выделяет столько временной памяти, как реализация в CLRS. Я должен сделать это, создав в начале только 1 временный массив и поместив в него все временные элементы при разделении и объединении.

Следует также отметить, что языком класса является Lua, что важно, поскольку единственными доступными структурами данных являются таблицы. Они похожи на карты Java в том, что они состоят из пар ключ-значение, но они похожи на массивы, в которых вам не нужно вставлять вещи парами - если вы вставляете только одну вещь, она рассматривается как значение, и ее ключ будет то, что его индекс будет в языке с реальными массивами. По крайней мере, я так понимаю, так как я новичок в Lua. Кроме того, все, что угодно, примитивы, строки, объекты и т. Д., Может быть ключом - даже разные типы в одной таблице.

Во всяком случае, 2 вещи, которые меня смущают:

Во-первых, ну, как это делается? Вы просто продолжаете переписывать временный массив с каждой рекурсией разделения и слияния?

Во-вторых, я действительно смущен инструкциями по выполнению домашних заданий (я провожу аудит класса бесплатно, поэтому не могу просить никого из сотрудников). Вот инструкции:

1. Напишите процедуру верхнего уровня merge_sort, которая принимает в качестве аргумента аргумент Луч сортировать. Он должен объявить временный массив и затем вызвать merge_sort_1, процедура из четырех аргументов: массив для сортировки, тот, который используется в качестве пространство и начальные и конечные индексы, в которых этот вызов merge_sort_1 должен работать.

2. Теперь напишите merge_sort_1, который вычисляет среднюю точку начала-конца интервал, и делает рекурсивный вызов для себя для каждой половины. После этого это вызовы слияния, чтобы объединить две половины. Процедура слияния, которую вы пишете сейчас, будет функцией постоянной массив и временный массив, начало, середина и конец. Он поддерживает индекс во временном массиве и индексы i, j в каждом (отсортировано) половина постоянного массива. Нужно пройтись по временному массиву от начала до конца, копируя значение либо из нижней половины постоянного массива, либо из верхняя половина постоянного массива. Он выбирает значение в нижнем половина, если это меньше или равно значению при j в верхней половине, и авансы я. Это выбирает значение в j в верхней половине, если это меньше, чем значение в нижней половине, и продвигается j. После того, как одна часть постоянного массива будет израсходована, обязательно скопируйте остальные другой части. В учебнике используется трюк с бесконечным значением ∞ для не проверяйте, израсходована ли какая-либо часть Однако этот трюк сложен подать заявку здесь, так как где бы вы положили? Наконец, скопируйте все значения от начала до конца во временном массиве вернуться к постоянному массиву.

Номер 2 сбивает с толку, потому что я понятия не имею, что должен делать merge_sort_1 и почему он должен отличаться от метода merge_sort. Я также не знаю, почему нужно передавать начальный и конечный индексы. На самом деле, может быть, я что-то неправильно понял, но инструкции звучат так, будто merge_sort_1 не выполняет никакой реальной работы.

Кроме того, все назначение сбивает с толку, потому что я не вижу в инструкциях, где деление делается на две половины исходного массива. Или я неправильно понял mergesort?

Надеюсь, у меня есть смысл. Спасибо всем!

Answer 1

Ваша основная процедура сортировки будет выглядеть следующим образом: (извините, я не знаю Lua, поэтому я напишу немного Javaish-кода)

void merge_sort(int[] array) {
  int[] t = ...allocate a temporary array...
  merge_sort_1(array, 0, array.length, t);
}

merge_sort_1 принимает массив для сортировки, некоторыеначальный и конечный индексы, а также массив для использования во временном пространстве.Он выполняет фактические вызовы «разделяй и властвуй» и вызывает процедуру merge.Обратите внимание, что рекурсивные вызовы должны идти на merge_sort_1, а не на merge_sort, потому что вы не хотите размещать массив на каждом рекурсивном уровне, только один раз в начале процедуры сортировки слиянием.(В этом и заключается смысл деления сортировки слиянием на две подпрограммы.)

Я предоставлю вам возможность написать подпрограмму merge.Он должен взять исходный массив, который содержит 2 отсортированные части и временный массив, и отсортирует исходный массив.Самый простой способ сделать это - слить во временный массив, а затем просто скопировать его обратно, когда закончите.

Answer 2

Во-первых, я хотел бы убедиться, что вы понимаете mergesort.
Посмотрите на это объяснение с причудливой анимацией, чтобы помочь вам понять его.

Это их псевдокодовая версия:

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

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

Это очищает назначение?

Answer 3

Во-первых, ну, как это делается? Вы просто продолжайте переписывать временный массив с каждой рекурсией расщепления и слияния

Да, временный массив продолжает перезаписываться. Временной массив используется во время фазы слияния для хранения результатов слияния, которые затем копируются обратно в постоянный массив в конце слияния.

Номер 2 сбивает с толку, потому что у меня есть понятия не имею, что предполагается merge_sort_1 делать, и почему это должно быть отличается от метода merge_sort.

merge_sort_1 - рекурсивный центр рекурсивной сортировки слиянием. merge_sort будет только вспомогательной функцией, создающей временный массив и заполняющей начальные и конечные позиции.

Я тоже не знаю, зачем это нужно прошли начальный и конечный индексы. В может быть, я что-то неправильно понял, но инструкции звучат как merge_sort_1 не выполняет никакой реальной работы.

Кроме того, все назначение сбивает с толку, потому что я не вижу из инструкции, где расщепление сделано, чтобы сделать 2 половинки оригинала массив. Или я недопонимание сортировка слиянием?

Рекурсивная функция merge_sort_1 будет работать только на части переданного массива. Часть, над которой он работает, определяется начальным и конечным индексами. Средняя точка между началом и концом - это то, как массив разделяется, а затем снова разделяется при рекурсивных вызовах. После завершения рекурсивных вызовов для верхней и нижней половин две половины объединяются в массив temp, а затем копируются обратно в постоянный массив.

Мне удалось написать сортировку слиянием в Lua, как описано, и я могу прокомментировать мою реализацию. Похоже, что через инструкции были написаны, как будто они были комментариями или о реализации учителя.

Вот функция merge_sort. Как я уже сказал, это всего лишь функция удобства, и я чувствую, что проблема не в этом.

-- Write a top level procedure merge_sort that takes as its argument
-- the array to sort.
function merge_sort(a)
    -- It should declare a temporary array and then call merge_sort_1,
    -- a procedure of four arguments: The array to sort, the one to use
    -- as temporary space, and the start and finish indexes within which
    -- this call to merge_sort_1 should work.
    merge_sort_1(a,{},1,#a)
end