Ruby script to test sorting algorithms.

sort_test.rb

#! /usr/local/bin/ruby
# **************************************
# ソート処理各種テスト
# **************************************
#
class SortTest
  N = 100    # データ個数
  M = 10000  # 値 MAX ( M 未満 )
  L = 10000  # ソート試行回数

  def initialize
    # ヒープに追加する要素の配列を生成
    @base = Array.new
    N.times { |i| @base << Random.rand(N) + 1 }
    # 乱数の種を毎回同じ値で初期化するなら以下２行のように。
    #prng = Random.new(1234)
    #N.times { |i| @base << prng.rand(N) + 1 }
    # ベース配列出力
    display_base
    # 処理用配列
    @a = Array.new  # ソート処理用
    @h = Array.new  # ヒープ用
  end

  def exec
    # 基本交換法（バブル・ソート）
    printf("%-22s", "1  : Bubble Sort")
    sort_bubble
    # 基本選択法（直接選択法）
    printf("%-22s", "2  : Selection Sort")
    sort_selection
    # 基本挿入法
    printf("%-22s", "3  : Insertion Sort")
    sort_insertion
    # 改良交換法（クイック・ソート）
    printf("%-22s", "4  : Quick Sort")
    sort_quick
    # 改良選択法（ヒープ・ソート）（上方移動）
    printf("%-22s", "5-1: Heap Sort(Up)")
    sort_heap_up
    # 改良選択法（ヒープ・ソート）（下方移動）
    printf("%-22s", "5-2: Heap Sort(Down)")
    sort_heap_down
    # 改良挿入法（シェル・ソート）
    printf("%-22s", "6  : Shell Sort")
    sort_shell
  rescue => e
    raise
  end

  private

  # 基本交換法（バブル・ソート）
  def sort_bubble
    # 処理開始時刻
    t1 = Time.now
    # 指定回数 LOOP
    L.times do |l|
      # 配列コピー
      #@a = @base.clone
      @a = Marshal.load(Marshal.dump(@base))
      # ソート処理
      0.upto(N - 2) do |i|
        (N - 1).downto(i + 1) do |j|
          @a[j - 1], @a[j] = @a[j], @a[j - 1] if @a[j] < @a[j - 1]
        end
      end
    end
    # 処理時間計算・結果出力
    t2 = Time.now
    display(0, @a, t2 - t1)
  rescue => e
    raise
  end

  # 基本選択法（直接選択法）
  def sort_selection
    # 処理開始時刻
    t1 = Time.now
    # 指定回数 LOOP
    L.times do |l|
      # 配列コピー
      #@a = @base.clone
      @a = Marshal.load(Marshal.dump(@base))
      # ソート処理
      0.upto(N - 2) do |i|
        min, s = @a[i], i
        (i + 1).upto(N - 1) do |j|
          min, s = @a[j], j if @a[j] < min
        end
        @a[i], @a[s] = @a[s], @a[i]
      end
    end
    # 処理時間計算・結果出力
    t2 = Time.now
    display(0, @a, t2 - t1)
  rescue => e
    raise
  end

  # 基本挿入法
  def sort_insertion
    # 処理開始時刻
    t1 = Time.now
    # 指定回数 LOOP
    L.times do |l|
      # 配列コピー
      #@a = @base.clone
      @a = Marshal.load(Marshal.dump(@base))
      # ソート処理
      1.upto(N - 1) do |i|
        (i - 1).downto(0) do |j|
          if @a[j] > @a[j + 1]
            @a[j], @a[j + 1] = @a[j + 1], @a[j]
          else
            break
          end
        end
      end
    end
    # 処理時間計算・結果出力
    t2 = Time.now
    display(0, @a, t2 - t1)
  rescue => e
    raise
  end

  # 改良交換法 (クイック・ソート)
  def sort_quick
    # 処理開始時刻
    t1 = Time.now
    # 指定回数 LOOP
    L.times do |l|
      # 配列コピー
      #@a = @base.clone
      @a = Marshal.load(Marshal.dump(@base))
      # ソート処理
      quick(0, N - 1)
    end
    # 処理時間計算・結果出力
    t2 = Time.now
    display(0, @a, t2 - t1)
  rescue => e
    raise
  end

  # 改良選択法 (ヒープ・ソート)(上方移動)
  def sort_heap_up
    # 処理開始時刻
    t1 = Time.now
    # 指定回数 LOOP
    L.times do |l|
      # 初期ヒープ作成(上方移動)
      generate_heap_up
      # ソート処理
      n, m = N, N  # データ個数、n の保存
      while n > 1
        @h[1], @h[n] = @h[n], @h[1]
        n -= 1     # 木の終端切り離し
        p = 1; s = 2 * p
        while s <= n
          s += 1 if s < n && @h[s + 1] > @h[s]
          break if @h[p] >= @h[s]
          @h[p], @h[s] = @h[s], @h[p]
          p = s; s = 2 * p
        end
      end
    end
    # 処理時間計算・結果出力
    t2 = Time.now
    display(1, @h, t2 - t1)
  rescue => e
    raise
  end

  # 改良選択法 (ヒープ・ソート)(下方移動)
  def sort_heap_down
    # 処理開始時刻
    t1 = Time.now
    # 指定回数 LOOP
    L.times do |l|
      # 元の配列を元の木としてコピー
      1.upto(N) { |i| @h[i] = @base[i - 1] }
      # 初期ヒープ作成(下方移動)
      generate_heap_down
      # ソート処理
      n, m = N, N  # データ個数, n の保存
      while n > 1
        @h[1], @h[n] = @h[n], @h[1]
        n -= 1     # 木の終端切り離し
        p = 1; s = 2 * p
        while s <= n
          s += 1 if s < n && @h[s + 1] > @h[s]
          break if @h[p] >= @h[s]
          @h[p], @h[s] = @h[s], @h[p]
          p = s; s = 2 * p
        end
      end
    end
    # 処理時間計算・結果出力
    t2 = Time.now
    display(1, @h, t2 - t1)
  rescue => e
    raise
  end

  # 改良挿入法 (シェル・ソート)
  def sort_shell
    # 処理開始時刻
    t1 = Time.now
    # 指定回数 LOOP
    L.times do |l|
      # 配列コピー
      #@a = @base.clone
      @a = Marshal.load(Marshal.dump(@base))
      # ソート処理
      gap = N / 2
      while gap > 0
        0.upto(gap - 1) do |k|
          i = k + gap
          while i < N
            j = i - gap
            while j >= k
              if @a[j] > @a[j + gap]
                @a[j], @a[j + gap] = @a[j + gap], @a[j]
              else
                break
              end
              j -= gap
            end
            i += gap
          end
        end
        gap /= 2
      end
    end
    # 処理時間計算・結果出力
    t2 = Time.now
    display(0, @a, t2 - t1)
  rescue => e
    raise
  end

  # クイック・ソート用再帰関数
  def quick(left, right)
    return unless left < right
    # 最左項を軸に. 軸より小さいグループ. 軸より大きいグループ.
    s, i, j = @a[left], left, right + 1
    loop do
      i += 1; i += 1 while @a[i] && @a[i] < s
      j -= 1; j -= 1 while @a[j] && @a[j] > s
      break if i >= j
      @a[i], @a[j] = @a[j], @a[i]
    end
    @a[left], @a[j] = @a[j], s  # 軸を正しい位置に挿入
    quick(left, j - 1)          # 左部分列に対する再帰呼び出し
    quick(j + 1, right)         # 右部分列に対する再帰呼び出し
  rescue => e
    raise
  end

  # ヒープ・ソート用ヒープ生成（上方移動）関数
  def generate_heap_up
    1.upto(N) do |i|
      # 元データ配列から１つヒープ要素として追加
      @h[i] = @base[i - 1]
      s = i        # 追加の位置
      p = s / 2    # 親要素の位置
      while s >= 2 && @h[p] < @h[s]
        @h[p], @h[s] = @h[s], @h[p]
        s = p      # 追加要素の位置
        p = s / 2  # 親要素の位置
      end
    end
  rescue => e
    raise
  end

  # ヒープ・ソート用ヒープ生成（下方移動）関数
  def generate_heap_down
    n = N          # データ個数
    (n / 2).downto(1) do |i|
      p = i        # 親要素の位置
      s = 2 * p    # 左の子要素の位置
      while s <= n
        s += 1 if s < n && @h[s + 1] > @h[s]  # 左右子要素の小さい方
        break if @h[p] >= @h[s]
        @h[p], @h[s] = @h[s], @h[p]  # 交換
        p = s      # 親要素の位置
        s = 2 * p  # 左の子要素の位置
      end
    end
  rescue => e
    raise
  end

  # ベース配列出力
  #   param: 配列
  def display_base
    puts "#### Base Array"
    0.upto(N - 1) do |i|
      printf("%5d ", @base[i])
      puts if (i + 1)  % 10 == 0 || i == N - 1
    end
    puts
  rescue => e
    raise
  end

  # 結果出力
  #   param: 0(Heap 以外配列), 1(Heap 配列)
  #          配列
  #          経過時間
  def display(k, ary, tt)
    # ソート結果出力出力 ( 必要ならコメント解除 )
    #puts
    #k.upto(N - 1 + k) do |i|
    #  printf("%5d ", ary[i])
    #  puts if (i + 1 - k)  % 10 == 0 || i == N - 1 + k
    #end
    # 経過時間出力
    puts "Time: %6.2f sec." % tt
  rescue => e
    raise
  end
end

if __FILE__ == $0
  begin
    SortTest.new.exec
  rescue => e
    $stderr.puts "[#{e.class}] #{e.message}"
    e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
  end
end