RubyでクイックソートとRSpecでそのテストを書いてみる

Rubyでクイックソートを書いてみます。

require 'benchmark'

class Array
  def qsort
    return self if self.size <= 1
    mark = self[0]
    right = Array.new
    left = Array.new
    (1..self.size-1).each do |i|
      if self[i] <= mark
        left.push(self[i])
      else
        right.push(self[i])
      end
    end
    left = left.qsort 
    right = right.qsort
    return left + [mark] + right
  end

  def test
    Benchmark.bm(10) do |x|
      x.report("Array#qsort (org): ") { self.qsort }
      x.report("Array#sort      (lib): ") { self.sort }
    end
  end
end

標準のArray#sortメソッドとのベンチマーク比較用メソッドもついでに。これ、めちゃくちゃ早い。だいぶ差があるみたいだし、計算自体はCで行っているのかな。

与えられる数字列の順番がある程度予測がつくなら、以下のように一番最初にとる例と真ん中にとったり、または最後にとったりと改変したほうが速くなる可能性が高い。（左の配列と右の配列きれいに分かれるとその分探索する深さが小さくなって済む）

 # 最初にセット
    pivot = self[0]

 # 配列の真ん中にセット
    pivot = self[self.size/2]

RSpecでテストコードを書く

上記で実装したクイックソートのテストコードをRSpecで実装します。

RSpecのRailsとかに組み込まれたことない感じの使い方はこの記事がすごく参考になりました。

Ruby - はじめてのRSpec - まずテスト書いてからコード書くシンプルなチュートリアル - Qiita

テストしたいプログラムのあるディレクトリのルートで以下のコマンドを実行してrspec用のディレクトリとhelperを作成します。

$ rspec --init

さっきのソートのテストコード。一個の例を出して通るかどうか確認しているだけなので、テストとしては不十分だけど、とりあえずということで。

require 'spec_helper'
require 'qsort'

describe "QuickSort Test" do
  it "Is sorted [9,4,2,0,1,6,7] to [0,1,2,4,6,7,9]" do
    example = [9,4,2,0,1,6,7]
    expect(example.qsort).to eq [0,1,2,4,6,7,9]
  end
end