Ruby バブルソート

バブルソートとは

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）[wikipedea引用]

基本的な考え方

1. 先頭から順に見ていって、左右の並びがおかしいところがあれば、入れ替える。

2. 最後までたどり着いたら再び先頭に戻って、同じように見ていく。

3. 1度も並び替えをすることなく先頭から最後まで見終わったら完了。

実装

class BubbleSort
  def initialize(array)
    @target = array
  end

  def sort
    flag = nil
    # flagがtrueである間,左右の比較交換を繰り返す
    begin
      flag = false
      (@target.size - 1).times do |i|
        if @target[i] > @target[i + 1]
          flag = true
          j = @target[i]
          @target[i] =@target[i + 1]
          @target[i + 1] = j
        end
      end
    end while(flag)
  end
end


# ---------- Main
if __FILE__ == $0
  N = 10
  puts "乱数を生成します"
  array = Array.new(N)
  array.each_index do |i|
    array[i] = rand(1000)
  end


  p array
  s = BubbleSort.new(array)


      puts "並び替え開始"
  s.sort
  puts "終了"
  p array
end

<実行結果>

乱数を生成します
[590, 441, 544, 452, 867, 362, 593, 11, 456, 217]
並び替え開始
終了
[11, 217, 362, 441, 452, 456, 544, 590, 593, 867]