Buno Journals

It's what I do that defines me.

Rubyでマージソート

bunoacts.hatenablog.com

クイックソートは、元データの並び方が悪いと、ソートの効率がバブルソートと大差がなくなってしまう(最悪時間計算量が O(n2)

こんな場合、より効率的にソートできるアルゴリズムマージソートである。

マージソートの流れを簡単に説明すると、

  1. 全体を小さなブロックに区切る
    1. 全体を2つに分ける
    2. 分けた2つを、さらにそれぞれ2つに分ける
    3. ブロックの大きさが1になるまで分け続ける
  2. 各ブロック同士をソートしながらつなぎ合わせる(マージ)
  3. 全体がソート済みになったら完了

f:id:bunoacts:20160527114339g:plain

WikipediaRubyの実装例があるので、コメント追記しながら処理を追ってみる。

マージソート - Wikipedia

def mergesort lst
    _mergesort_ lst.dup  # 副作用で配列が壊れるので、複製を渡す
end

def _mergesort_ lst
    return lst if (len = lst.size) <= 1

    # pop メソッドの返す値と副作用の両方を利用して、lst を二分する
    lst2 = lst.pop(len >> 1)

    _merge_(_mergesort_(lst), _mergesort_(lst2))
end

# 二つの配列をソートしてつなぎ合わせる(マージ)
def _merge_ lst1, lst2
    len1, len2 = lst1.size, lst2.size
    result = Array.new(len1 + len2)
    a, b = lst1[0], lst2[0]
    # i: マージ後の配列resultのインデックス
    # j: lst1のインデックス
    # k: lst2のインデックス
    i, j, k = 0, 0, 0
    loop {
        if a <= b
            result[i] = a
            i += 1 ; j += 1
            break unless j < len1
            a = lst1[j]
        else
            result[i] = b
            i += 1 ; k += 1
            break unless k < len2
            b = lst2[k]
        end
    }
    while j < len1 do
        result[i] = lst1[j]
        i += 1 ; j += 1
    end
    while k < len2 do
        result[i] = lst2[k]
        i += 1 ; k += 1
    end
    result
end

実行例

[2] pry(main)> ary = ('a'..'z').to_a.shuffle
=> ["h", "w", "y", "j", "c", "f", "g", "o", "p", "b", "q", "s", "e", "d", "a", "i", "z", "k", "n", "v", "x", "m", "u", "r", "l", "t"]
[3] pry(main)> mergesort(ary)
=> ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

参考書籍

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版