Рекурсивный слияние сортировки в Ruby

Question

Я пытаюсь написать рубиновый метод, который рекурсивно выполняет сортировку слияния. У меня есть метод работы, но это один из тех случаев, когда я случайно его работал, поэтому я понятия не имею, ПОЧЕМУ он работает, и мне хотелось бы понять, как работает код, который я написал. В psuedocode шаги, которые я выполнял, выглядели следующим образом.

1. Сплит исходный массив длины п, пока не имеет п массивы длины 1
2. Merge и сортировки 2 массивы длины т в момент времени, чтобы возвращать массив длины т * 2
3. Повторите этот шаг выше пока у меня нет ни одного сортированного массива длины n

В принципе, это похоже на то, что большое дерево разветвляется на n ветвей с каждой ветвью, содержащей массив длиной 1. Затем мне нужно взять эти n ветвей и каким-то образом объединить их обратно в одну ветвь внутри метода.

def merge_sort(arr) 
    return arr if arr.length == 1 
    merge(merge_sort(arr.slice(0, arr.length/2)), 
     merge_sort(arr.slice(arr.length/2, arr[-1]))) 
end 

def merge(arr1, arr2) 
    sorted = [] 
    begin 
    less_than = arr1[0] <=> arr2[0] 
    less_than = (arr1[0] == nil ? 1 : -1) if less_than == nil 
    case less_than 
    when -1 
     sorted << arr1[0] 
     arr1 = arr1.drop(1) 
    when 0 
     sorted << arr1[0] 
     sorted << arr2[0] 
     arr1 = arr1.drop(1) 
     arr2 = arr2.drop(1) 
    when 1 
     sorted << arr2[0] 
     arr2 = arr2.drop(1) 
    end 
    end until (arr1.length == 0 && arr2.length == 0) 
    sorted 
end 

merge_sort([1,6,3,8,22,3,11,24,54,68,79,80,98,65,46,76,53]) 

#Returns => [1, 3, 3, 6, 8, 11, 22, 24, 46, 53, 54, 65, 68, 76, 79, 80, 98] 

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

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

Answer 1

Вот моя реализация слияния в Рубине

def mergesort(array) 
    return array if array.length == 1 
    middle = array.length/2 
    merge mergesort(array[0...middle]), mergesort(array[middle..-1]) 
end 


def merge(left, right) 
    result = [] 
    until left.length == 0 || right.length == 0 do 
    result << (left.first <= right.first ? left.shift : right.shift) 
    end 
    result + left + right 
end 

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

Во-первых, у вас есть базовый футляр: return array if array.length == 1 Это то, что позволяет рекурсии работать, а не идти бесконечно.

Далее в моей реализации я определил переменную middle представлять середину массива: middle = array.length/2

Наконец, третья линия, где вся работа происходит: merge mergesort(array[0...middle]), mergesort(array[middle..-1])

Что вы здесь делаете говорит метод слияния, чтобы объединить объединенную левую половину с объединенной правой половиной.

Если вы предполагаете, что ваш входной массив равен [9, 1, 5, 4], то, что вы говорите, является merge mergesort([9, 1]), mergesort([5, 4]).

Для выполнения слияния вам сначала необходимо объединить функции [9, 1] и mergesort [5, 4]. Рекурсия становится

merge((merge mergesort([9]), mergesort([1])), (merge mergesort([5]), mergesort([4]))) 

Когда мы рекурсию снова, mergesort([9]) достиг базового варианта и возвращает [9]. Аналогично, mergesort([1]) также достиг базового футляра и возвращает [1]. Теперь вы можете объединить [9] и [1]. Результатом слияния является [1, 9].

Теперь для другой стороны слияния. Нам нужно выяснить результат merge mergesort([5]), mergesort([4]), прежде чем мы сможем объединить его с [1, 9].Следуя той же процедуре, что и левая сторона, мы перейдем к основному футляру [5] и [4] и слейте их, чтобы получить [4, 5].

Теперь нам необходимо объединить [1, 9] с [4, 5].

1. На первом проходе, result получает 1, потому что 1 < = 4.
2. На следующем проходе, мы работаем с result = [1], left = [9] и right = [4, 5]. Когда мы видим, что left.first <= right.first мы видим, что это неверно, мы возвращаем right.shift или 4. Теперь result = [1, 4].
3. На третьем проходе мы работаем с result = [1, 4], left = [9] и right = [5]. Когда мы видим, что left.first <= right.first мы видим, что это неверно, мы возвращаем right.shift или 5. Теперь result = [1, 4, 5].
4. Здесь петля заканчивается, потому что right.length == 0.
5. Мы просто объединяем result + left + right или [1, 4, 5] + [9] + [], что приводит к сортировке массива.