読者です 読者をやめる 読者になる 読者になる

Buno Journals

It's what I do that defines me.

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

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

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

プログラミングの宝箱 アルゴリズムとデータ構造 第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(n2) であることがわかります。

空間計算量

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

参考情報:

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

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

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