Ruby 병합정렬 구현

1 개요[ | ]

Ruby 병합정렬 구현

Ruby

Copy

def merge_sort(a, left=0, right=-1)
    def merge(a, left, middle, right)
        n1 = middle+1-left
        n2 = right-middle
        l = Array.new(n1,0)
        r = Array.new(n2,0)
        for i in (0...n1); l[i]=a[left+i]; end
        for i in (0...n2); r[i]=a[middle+1+i]; end
        i=j=0; k=left
        while i<n1 and j<n2
            if l[i]<=r[j] then a[k]=l[i]; i+=1; k+=1
            else a[k]=r[j]; j+=1; k+=1 end
        end
        while i<n1; a[k]=l[i]; i+=1; k+=1; end
        while j<n2; a[k]=r[j]; j+=1; k+=1; end
    end
    right=a.size-1 if right==-1
    return if left>=right
    middle = (left+right-1)/2
    merge_sort(a, left, middle)
    merge_sort(a, middle+1, right)
    merge(a, left, middle, right)
end
arr = [9,1,22,4,0,-1,1,22,100,10]
merge_sort(arr)
print arr
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

Ruby

Copy

def merge(a, left, middle, right)
    n1 = middle+1-left
    n2 = right-middle
    l = Array.new(n1,0)
    r = Array.new(n2,0)
    for i in (0...n1); l[i]=a[left+i]; end
    for i in (0...n2); r[i]=a[middle+1+i]; end
    i=j=0; k=left
    while i<n1 and j<n2
        if l[i]<=r[j] then a[k]=l[i]; i+=1; k+=1
        else a[k]=r[j]; j+=1; k+=1 end
    end
    while i<n1; a[k]=l[i]; i+=1; k+=1; end
    while j<n2; a[k]=r[j]; j+=1; k+=1; end
end
def merge_sort(a, left=0, right=-1)
    right=a.size-1 if right==-1
    return if left>=right
    middle = (left+right-1)/2
    merge_sort(a, left, middle)
    merge_sort(a, middle+1, right)
    merge(a, left, middle, right)
end
arr = [9,1,22,4,0,-1,1,22,100,10]
merge_sort(arr)
print arr
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

2 같이 보기[ | ]