Алгоритм сортировки с использованием рекурсии

Question

Я делаю проект «Один». Проблема заключается в следующем: создать алгоритм сортировки слияния с использованием рекурсии. Далее модифицируются из чьего-то решения:

def merge_sort(arry) 
    # kick out the odds or kick out of the recursive splitting? 
    # I wasn't able to get the recombination to work within the same method. 
    return arry if arry.length == 1 
    arry1 = merge_sort(arry[0...arry.length/2]) 
    arry2 = merge_sort(arry[arry.length/2..-1]) 
    f_arry = [] 
    index1 = 0 # placekeeper for iterating through arry1 
    index2 = 0 # placekeeper for iterating through arry2 
    # stops when f_arry is as long as combined subarrays 
    while f_arry.length < (arry1.length + arry2.length) 
    if index1 == arry1.length 
     # pushes remainder of arry2 to f_arry 
     # not sure why it needs to be flatten(ed)! 
     (f_arry << arry2[index2..-1]).flatten! 
    elsif index2 == arry2.length 
     (f_arry << arry1[index1..-1]).flatten! 
    elsif arry1[index1] <= arry2[index2] 
     f_arry << arry1[index1] 
     index1 += 1 
    else 
     f_arry << arry2 [index2] 
     index2 += 1 
    end 
    end 
    return f_arry 
end 

1. ли первая линия return arry if arry.length == 1 пинать его из рекурсивного разбиения массива (ов), а затем в обходе рекурсивного расщепления части методы, чтобы вернуться к раздел рекомбинации? Похоже, он должен просто продолжать повторять его, как только он вернется в этот раздел, когда он повторится.

2. Почему это должно быть flatten -ed?

Answer 1

Самый простой способ понять первую строку, чтобы понять, что единственный контракт, который merge_sort обязан это «вернуть отсортированный массив» - если массив имеет только один элемент (arry.length == 1) это уже отсортировано - так что ничего не нужно делать! Просто верните массив.

В рекурсии это называется «Условие останова». Если вы не предоставляете условие остановки - рекурсия никогда не закончится (поскольку она всегда будет называть себя и никогда не возвращается)!

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

arr = [1] 
arr << [2, 3] 
# => [1, [2, 3]] 

Если вы пытаетесь сгладить получившийся массив только в конце итерации , а не как вы добавляете элементы, вы будете иметь проблемы, так как его длина будет перекос:

arr = [1, [2, 3]] 
arr.length 
# => 2 

Хотя arr содержит три номеров у него есть только два элемента - и это нарушит ваше решение.

Вы хотите, чтобы все элементы в вашем массиве были номерами, а не массивами. flatten! гарантирует, что все элементы в массиве являются атомами, и если они не являются, это добавляет элементы дочернего массива до себя вместо детского массива:

arr.flatten! 
# => [1, 2, 3] 

Другим вы вариант вы можете рассмотреть (и будут быть более эффективным) является использование вместо concat:

arr = [1] 
arr.concat([2, 3]) 
# => [1, 2, 3] 

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