nekoTheShadow’s diary

IT業界の片隅でひっそり生きるシステムエンジニアです(´・ω・｀)

rubyでクイックソートを短く実装しましょう。

ruby

　以前はユークリッドの互除法をわかりやすさを担保しつつ、できるだけ短く実装しました。

　今回は同じことをクイックソートでしてみようという記事になります。

そもそもクイックソートって?

　クイックソートはその名の通りソートアルゴリズムのひとつです。バブルソート、挿入ソート、コムソートなどなど、ソートの方法はさまざまありますが、そのなかでもクイックソートは高速に動作し、かつ再帰を利用するためプログラミングの勉強にはもってこいのアルゴリズムなのです。

　具体的な手順は次のようになります。

  1. リストからひとつ数値を取り出し、ピボット(基準値)とする。
    • リストの左端などがピボットとして採用されることが多い。
  2. リストの要素をピボットより大きいものと小さいものに分ける。
    • つまり「ピボットより大きい要素を集めたリスト」「ピボットより小さい要素を集めたリスト」を作るわけである。
  3. 2.で作られたふたつのリストをソートする。
  4. ソート済みの「ピボットより小さい要素を集めたリスト」と「ピボットより大きい要素を集めたリスト」を連結して完成。

　正直なところことばで説明するには限界があるので、rubyで「べた」に実装してみたいと思います。

class Array
    
    def quick_sort
        # 再帰用のおまじない。
        # レシーバが空、もしくは要素が1つのみの場合はレシーバをそのまま返す。
        return self if self.size < 2
        
        # ピボットを設定する。
        pivot = self.shift
        
        # それぞれピボットより大きい要素、小さい要素を格納する配列。
        smallers = []
        biggers = []
        self.each do |num|
            if num < pivot
                smallers << num
            else # num >= pivot
                biggers << num
            end
        end
        
        # smallersとbiggersをそれぞれソートして連結。
        smallers.quick_sort + [pivot] + biggers.quick_sort
        
    end
end

p [3,2,1,5,4].quick_sort #=> [1, 2, 3, 4, 5]

　難しいことをやっているという印象はそれほど受けませんね。

どのように短くしていくのか

　上の例では限りなく「べた」に実装しましたが、それをrubyの便利メソッドを使って短くかつ分かりやすく実装してみましょう。

class Array
    
    def quick_sort
        return self if self.size < 2
        pivot = self.shift
        self.partition{|num| num < pivot}.map(&:quick_sort).insert(1,pivot).flatten
    end

end

p [3,2,5,4,1].quick_sort #=> [1, 2, 3, 4, 5]

　全部で3行になりました――といっても上2行は全く同じ。つまり「べた」な例では長々書いた「ピボット設定」より後の処理をワンライナーにしたというだけです。

具体的な解説

　この「ワンライナー」部分がどうなっているのかを具体的に解説してみたいと思います。まず次の表を見てください――というより次の表がすべてだったりします。

メソッド レシーバ 戻り値
partition [2,5,4,1] [[2,1],[5,4]]
map [[2,1],[5,4]] [[1,2],[4,5]]
insert [[1,2],[4,5]] [[1,2],3,[4,5]]
flatten [[1,2],3,[4,5]] [1,2,3,4,5]

　「レシーバ」と「戻り値」を順番に追いかけるとわかりやすいと思います。

　次に詳しい説明も乗せておきます。

  1. partitionはレシーバの要素を順次ブロックに引き渡し、ブロックが「真を返した要素」と「偽を返した要素」に分けるメソッドです。
    • [1,2,3].partition{|num| num.odd?} => [[1,3],[2]]
    • [2,5,4,1].partition{|num| num < pivot} => [[2,1],[5,4]]はpivot = 3より「小さいもの」と「それ以外」に分けているということになります。

  2. mapはレシーバの要素を順次ブロックに引き渡し、ブロックの戻り値を配列に格納するメソッドです。

    • [1,2,3,4].map{|num| num * 2} => [2,4,6,8]
    • [[2,1],[5,4]].map(&:quick_sort) => [[1,2],[4,5]]ではふたつの配列[2,1]と[5,4]に対してquick_sortを再帰的に実行、その結果を配列に収めて戻り値としています。
      • メソッドの引数に&(アンパサンド) + Symbol(メソッド名)をとる理由や意味合いについては長くなるので、ここでは省略します。

  3. insertは第1引数で指定した位置に第2引数で指定した要素を代入する破壊的なメソッドです。

    • [0,1,2].insert(1,100) => [0,100,1,2]
      • 「第1引数で指定したインデックスに第2引数で指定した要素を代入、それより右の要素は全部右にずれる」と覚えるとよいでしょう。
    • [[1,2],[4,5]].insert(1,pivot) => [[1,2],3,[4,5]]では、self[1]にpivot = 3を代入し、[4,5]を右にずらしています。
  4. flattenは配列を平坦化します。
    • [[1],[[2],3],4].flatten => [1,2,3,4]
    • [[1,2],3,[4,5]].flatten => [1,2,3,4,5]についてはもういうまでもありませんね。

　ちょっと蛇足が混じったような気もしますが、おおよその説明はできたはず。