Ruby

バブルソート

問
バブルソートのアルゴリズムを使って配列dataの値を昇順に並べ替えるプログラムを、以下のコードに追記する形で実装してください。

class Array
  def swap!(a,b)
    tmp = self[a]
    self[a] = self[b]
    self[b] = tmp
  end
end

data = (1..10).to_a.shuffle
puts data.to_s

# ここに実装

puts data.to_s
バブルソートのアルゴリズム（Wikipediaより抜粋）：
要素の1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。

Arrayクラスに追加した「swap!」メソッドは指定されたインデックスの要素を入れ替えるためのメソッドです。必要に応じて利用してください。

解答例
バブルソートには様々な実装方法がありますが、Wikipediaに掲載されていた擬似コードを参考にしてRubyで書きなおした実装が以下になります。配列の添字は「0」から始まっている点に注意してください。

class Array
  def swap!(a,b)
    tmp = self[a]
    self[a] = self[b]
    self[b] = tmp
  end
end

data = (1..10).to_a.shuffle
puts data.to_s

for i in (0...data.length)
  for j in (1...data.length)
    if data[j] < data[j-1] then
      data.swap!(j,j-1)
    end
  end
end

puts data.to_s

別解
「並べ替えが発生しなくなったら」という条件を素直に実装したバージョンです。swappedというフラグを用意して、フラグがtrueにならなくなったらループを終了(break)しています。

while true
  swapped = false
  for j in (1...data.length)
    if data[j] < data[j-1] then
      data.swap!(j,j-1)
      swapped = true
    end
  end
  break unless swapped
end

こちらはforをeachに書き換えたバージョンです。教科書で触れられている通り、forはeachのシンタックスシュガーですので、常に置き換え可能です。

(0...data.length).each do |i|
  (1...data.length).each do |j|
    if data[j] < data[j-1] then
      data.swap!(j,j-1)
    end
  end
end

参考URL