素朴なソートアルゴリズムメニュー

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

FINAL問題挿入ソート

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

n = gets.to_i
a = gets.split.map(&:to_i)
insertion_sort(a, n)

問題文の疑似コードをRubyに書き直しています。
Rubyではdefを使うことでメソッドを定義できます。

FINAL問題選択ソート

def selection_sort(a, n)
    for i in 0..n - 2
        min_index = i
        for j in i + 1..n - 1
            if a[j] < a[min_index]
                min_index = j
            end
        end
        a[i], a[min_index] = a[min_index], a[i]
        puts a.join(' ')
    end
end

n = gets.to_i
a = gets.split.map(&:to_i)
selection_sort(a, n)

swapはそれぞれをの数値を=で入れ替える処理しています。

FINAL問題バブルソート

def bubble_sort(a, n)
    for i in 0..n-2
        for j in (n - 1).downto(i + 1)
            if a[j - 1] > a[j]
                a[j - 1], a[j] = a[j], a[j - 1]
            end
        end
        puts a.join(' ')
    end
end
n = gets.to_i
a = gets.split.map(&:to_i)
bubble_sort(a, n)

今回の問題集で登場した素朴なソートはどれも効率が悪く、実行時間が少し長いです。