paizaラーニング解答: 効率的なソートアルゴリズムメニュー[Ruby]

効率的なソートアルゴリズムメニュー

問題に挑戦する前に今回登場するソートアルゴリズムについて解説されている下記の講座に取り組むのがおすすめです。

FINAL問題 シェルソート

def insertion_sort(a, n, h)
    num_of_move = 0
    for i in h..n - 1
        x = a[i]
        j = i - h
        while j >= 0 && a[j] > x
            a[j + h] = a[j]
            j -= h
            num_of_move += 1
        end
        a[j + h] = x
    end
    puts num_of_move
end

def shell_sort(a, n, h)
    h.each do |i| 
        insertion_sort(a, n, i)
    end
end
        
n = gets.to_i
a = gets.split.map(&:to_i)
k = gets.to_i
h = gets.split.map(&:to_i)
shell_sort(a, n, h)

FINAL問題 マージソート

$count = 0

def merge(a, left, mid, right)
    nl = mid - left
    nr = right - mid
    
    l = []
    r = []
    for i in 0..nl - 1
        l[i] = a[left + i]
    end
    for i in 0..nr - 1
        r[i] = a[mid + i]
    end
    
    l << Float::INFINITY
    r << Float::INFINITY
    
    lindex = 0
    rindex = 0

    (left...right).each do |i|
        if l[lindex] < r[rindex]
            a[i] = l[lindex]
            lindex += 1
        else
            a[i] = r[rindex]
            rindex += 1
            $count += 1
        end
    end
end

def merge_sort(a, left, right)
    if left + 1 < right
    mid = (left + right) / 2
    merge_sort(a, left, mid)
    merge_sort(a, mid, right)
    merge(a, left, mid, right)
  end
end

n = gets.to_i
a = gets.split.map(&:to_i)
merge_sort(a, 0, n)
puts a.join(' ')
puts $count

メソッドの外はスコープ外なのでcountは$を先頭に付けてグローバル変数にする必要があります。
番兵はFloat::INFINITYで無限大にします。

FINAL問題 クイックソート

$count = 0

def quick_sort(a, left, right)
    if left + 1 >= right
        return
    end

    pivot = a[right - 1]
    cur_index = left

    for i in left..right - 2
        if a[i] < pivot
            a[cur_index], a[i] = a[i], a[cur_index]
            cur_index += 1
            $count += 1
        end
    end

    a[cur_index], a[right - 1] = a[right - 1], a[cur_index]
    quick_sort(a, left, cur_index)
    quick_sort(a, cur_index + 1, right)
end

n = gets.to_i
a = gets.split.map(&:to_i)
quick_sort(a, 0, n)
puts a.join(' ')
puts $count