単純交換ソート

となりの要素が大きければ、となりの要素と交換を繰り返す。
計算量はO(n^2)。
安定的なアルゴリズム。

#最後に入れ替えが発生した場所を記憶しておくことで、
#それより前の場所では入れ替えの必要がないことが分かる。
#今回は実装していない。

def bubblesort!(array)
  1.step(array.size - 1, 1) do |i|
    exchanged = false
    (array.size - 1).step(i, -1) do |j|
      if(array[j] < array[j - 1]) then
        #現在の要素と１つ前の要素を比較し、必要なら入れ替える
        tmp = array[j - 1]
        array[j - 1] = array[j]
	array[j] = tmp
        exchanged = true
      end
    end
    break unless exchanged	#入れ替えが発生していない場合はそれ以上ソートの必要はない
  end
  return array
end

data = Array.new
while input = $stdin.gets.to_i
  break if input < 0 #負数が入力されたら入力の受付を終了する
  data << input
end

p data
bubblesort!(data)
p data