『アルゴリズムとデータ構造』学習ノート：バブルソート

バブルソート

バブルソート

隣り合う２つのデータを比較して、前の要素の方が大きかった場合、後ろの要素と交換する。

このアクションを先頭から順に繰り返すことで、要素を整列させるソート方法。小さい要素が泡のように上がってくることから、こう名付けられた。

バブルソートは要素の数が小さいときは良いが、要素の数が大きくなればなるほど処理速度が遅くなる性質を持つ。

（例）[2,3,1,5,4]　→　[2,1,3,5,4]　→　[2,1,3,4,5]　→　[1,2,3,4,5]

書籍内のサンプルコードはC言語で書かれていたが、学習のためRubyで書きなおしてみた。

# coding: utf-8
N = 10 # 配列の数
data = Array.new(N)

def bubble_sort(data)
  loop do
    flag = 0 # 並び替えが起こったか否かの検証
    j = 0
    while N-1 > j do
      if data[j] > data[j+1]
        flag = 1
        tmp = data[j]
        data[j] = data[j+1]
        data[j+1] = tmp
      end
      j = j + 1
    end
      return data if flag == 0
  end
end

puts "ソート準備！"

# 乱数を生成して配列に格納する
i = 0
while N > i do
  data[i] = rand(10000000)
  i = i + 1
end

# 生成した配列を出力
data.each do |d|
  puts d
end

puts "ソート開始....."

# ソート（bubble_sortメソッドの呼び出し）
data2 = bubble_sort(data)

data2.each do |d|
  puts d
end

puts "ソート終了！"