バブルソート(bubble sort)

隣り合う値を比較して入れ換えていき、右端から確定していく。
最初は再帰で書いてたんだけど必要ないことに気がついた。配列を汚染しないように dup でコピーを作ってからにしてみた。

def bubble_sort(list)
  dup = list.dup
  (dup.length - 1).downto(0) {|limit|
    0.upto(limit - 1) {|i|
      if dup[i] > dup[i + 1]
        tmp = dup[i + 1]
        dup[i + 1] = dup[i]
        dup[i] = tmp
      end
    }
  }
  dup
end

バブルソートの語源

上にまとめた表をよく眺めると、ステップが進むにつれて、大きな値が左から右に移動しています。これを縦に並べて眺めると、丁度コップの中の泡(=バブル)が下から上って行くように見えるところからバブルソートと言われます。

整列　隣接交換法(バブルソート)と選択法(セレクションソート)

なんと！理解した！