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

概要

バブルソート

内容

基本交換法、隣接交換法ともいう。
最悪計算時間はO(N2)。

ソート仕様

・左端から順に隣り合う要素を比較し、左の方が大きければ右の要素と入れ替える。
・右端まで到達したら再度左端から比較を行う。
・要素数=Nとして、N回の比較をN回繰り返せば全体のソートが完了。

コード

bubble_sort.rb

# encoding: utf-8

class Array
  def bubble_sort
    (1..self.size).each do |cnt|
      self.each_with_index do |v, i|
        break if i == self.size - 1
        swap(i) if have_to_swap?(i)
      end
    end
    return self
  end

  private
  def have_to_swap?(i)
    self[i] > self[i + 1]
  end

  def swap(i)
    tmp_current = self[i]
    self[i] = self[i + 1]
    self[i + 1] = tmp_current
  end
end

テストコード

bubble_sort_spec.rb

# encoding: utf-8
require_relative "../bubble_sort"

describe Array do
  cases = [
    {
      input_ary: [5,4,3,2,1],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [1,2,3,4,5],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [1,4,3,2,5],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [2,4,3,5,1],
      expected: [1,2,3,4,5]
    },
    {
      input_ary: [3,4,5,2,1],
      expected: [1,2,3,4,5]
    }
  ]

  cases.each do |c|
    it "#bubble_sort" do
      actual = c[:input_ary].bubble_sort
      expect(actual).to eq(c[:expected])
    end
  end
end