【アルゴリズムの勉強】Rubyでバブルソートを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyでバブルソートを実装する。

バブルソートとは

ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソート - Wikipedia


Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count
# 降順, 昇順
ASC, DESC = 1, 2

def bubble_sort(arr, number_of_elements, order)
  for i in 1..(number_of_elements - 1)
    (number_of_elements - i).times{|j|
      if order == ASC
        if (arr[j] > arr[j + 1])
          arr[j], arr[j + 1] = arr[j + 1], arr[j]
        end
      elsif order == DESC
        if (arr[j] < arr[j + 1])
          arr[j], arr[j + 1] = arr[j + 1], arr[j]
        end
      end
    }
  end
  return arr
end

asc_sorted_arr = bubble_sort(arr, number_of_elements, ASC)
p asc_sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
desc_sorted_arr = bubble_sort(arr, number_of_elements, DESC)
p desc_sorted_arr
# => [60, 25, 20, 15, 12, 10, 9, 6, 4, 2]

参考文献