Rubyでアルゴリズムやらデータ構造やらのお勉強（Bubble Sort）

bubble_sort.rb

# -*- coding: utf-8 -*-

# Cで書かれたアルゴリズムやらデータ構造なりを、自分なりにRubyで表現してみるお勉強PJ。
# 参考書籍（プログラミングの宝箱 アルゴリズムとデータ構造）
# Ruby1.9.3で動作確認済み

$VERBOSE = true

class Array

  def bubble_sort!
    sorted = false

    until sorted
      sorted = true

      (length - 1).times do |index|
        point = self[index]
        succ  = self[index + 1]

        if point > succ
          sorted = false
          self[index]     = succ
          self[index + 1] = point
        end
      end
    end
    
    self
  end

  def fixed_bubble_sort!
    sorted = false
    shift_size = 0

    until sorted
      sorted = true
      shift_size += 1

      (length - shift_size).times do |index|
        point = self[index]
        succ  = self[index + 1]

        if point > succ
          sorted = false
          self[index]     = succ
          self[index + 1] = point
        end
      end
    end
    
    self
  end

end

# Overview

list = (-50..50).to_a.shuffle
p list
list2, list3 = list.dup, list.dup

p list.object_id
p list.bubble_sort!
p list.object_id

p list2.object_id
p list2.fixed_bubble_sort!
p list2.object_id

p list3.object_id
p list3.sort!
p list3.object_id

# Benchmark

require 'benchmark'

Benchmark.bm do |bm|
  list = (-100..100).to_a.shuffle

  bm.report 'BubbleSort in Ruby' do
    10.times do
      list.dup.bubble_sort!
    end
  end

  bm.report 'Fixed BubbleSort in Ruby' do
    10.times do
      list.dup.fixed_bubble_sort!
    end
  end

  bm.report "Ruby's Sort" do
    10.times do
      list.dup.sort!
    end
  end
end

# Benched on MyPC
#   BubbleSort in Ruby  0.180000   0.000000   0.180000 (  0.177473)
#   Fixed BubbleSort in Ruby  0.120000   0.000000   0.120000 (  0.121827)
#   Ruby's Sort  0.000000   0.000000   0.000000 (  0.000311)

もし本当にこういうメソッドがあった場合、ソートかからなかったときはnilを返すべきだけど、ここでは気にしない。