Реализация сортировки слиянием Julia работает неправильно - PullRequest
Новая
       21

Реализация сортировки слиянием Julia работает неправильно

0 голосов
/ 20 сентября 2018

Я не совсем уверен, почему моя реализация сортировки слиянием не работает.

merge_sort принимает в качестве аргументов массив A, а также начальный и конечный индексы p и r.Если я попытаюсь запустить merge_sort (A, 1, 9) для A = [1, 64, 64, 315, 14, 2, 3, 4, 5], A станет A = [1, 1, 1, 1,1, 2, 2, 4, 5].Я пытаюсь использовать дозорный, чтобы определить, не были ли исчерпаны массивы L и R.

Вот код: 

function merge_sort(A, p, r)
    if p < r
        q = floor(Int, (p+r)/2)
        merge_sort(A, p, q)
        merge_sort(A, q+1, r)
        merge(A, p, q, r)
    end
end



function merge(A, p, q, r)
    n1 = q-p+1
    n2 = r-q
    L = []
    R = []

    for i = 1:n1
      push!(L, A[p+1-1])
    end

    for j = 1:n2
      push!(R, A[q+j])
    end

    sentinel = 123456789
    push!(L, sentinel)
    push!(R, sentinel)
    i=1
    j=1

    for k=p:r
      if L[i] <= R[j]
         A[k] = L[i]
         i = i+1
      else
        A[k] = R[j]
        j = j+1

      end
    end
end

1 Ответ

0 голосов
/ 20 сентября 2018

У вас есть опечатка в push!(L, A[p+1-1]), которая должна быть push!(L, A[p+i-1]).

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

function merge_sort!(A, p = 1, r = length(A))
    if p < r
        q = div(p+r, 2)
        merge_sort!(A, p, q)
        merge_sort!(A, q+1, r)
        merge!(A, p, q, r)
    end
    A
end

function merge!(A, p, q, r)
    sentinel = typemax(eltype(A))
    L = A[p:q]
    R = A[(q+1):r]
    push!(L, sentinel)
    push!(R, sentinel)
    i, j = 1, 1
    for k in p:r
      if L[i] <= R[j]
          A[k] = L[i]
          i += 1
      else
          A[k] = R[j]
          j += 1
      end
    end
end
...