Rubyでバブルソートを書いてみる

バブルソートのアルゴリズム

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

書籍を参考にバブルソートのアルゴリズムをRubyで書いてみる。

（この書籍にはCとJavaのコードが載っている）

バブルコードの解説は以下のページも丁寧。

Oyster Harbor | バブルソート(Bubble sort)

簡単に流れを説明すると

1. 配列の先頭から、二つの要素を比較する。順序が不正であれば入れ替える。

2. 最後まで辿り着いたら、再び先頭から。

3. 一度も入れ替えが発生しなければソート完了。

Rubyのコード

配列を引数に取る関数として書くと

def bubble_sort(ary)
  begin
    swapped = false
    0.upto(ary.size - 2) do |i|
      if (ary[i] > ary[i + 1])
        ary[i], ary[i + 1] = ary[i + 1], ary[i]
        swapped = true
      end
    end
  end while swapped
  ary
end

だが、このやり方は「ループが1回終了するごとに、配列の後方がソート済みになってくる」ので、 この部分は調べる必要がない。

def bubble_sort(ary)
  k = 0  # k: 配列後方、ソート済み要素の数
  begin
    swapped = false
    0.upto(ary.size - 2 - k) do |i|
      if (ary[i] > ary[i + 1])
        ary[i], ary[i + 1] = ary[i + 1], ary[i]
        swapped = true
      end
    end
    k += 1
  end while swapped
  ary
end

実行例。

[2] pry(main)> ary = [*1..10].sort_by {rand}
=> [7, 3, 5, 6, 2, 10, 4, 8, 1, 9]
[3] pry(main)> bubble_sort(ary)
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

計算量

Oyster Harbor | バブルソート(Bubble sort) によると、

時間計算量

まず一つのデータの位置を確定するのに、 (n-1) 回の比較が必要です。 次は比較回数が1回少なくなるので、 (n-2) 回の比較が必要です。 これの繰り返しが平均時間計算量になります。...（中略）...

O(n²) であることがわかります。

空間計算量

空間計算量は内部ソートなので、外部メモリを使わずにソートできます。 必要なメモリはデータn個を格納するための領域のみです。 つまり、空間計算量は O(n) であることがわかります。

参考情報：

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

Oyster Harbor | バブルソート(Bubble sort)