単純なソートのおさらい（Ruby）

アルゴリズムを学ぼう

上から、バブルソート、選択ソート、挿入ソート。以前にも書いたのですが、おさらいということで。

class Array
  def bubble_sort
    ar = dup
    (ar.size - 1).downto(1) do |i|
      1.upto(i) {|j| ar[j - 1], ar[j] = ar[j], ar[j - 1] if ar[j - 1] > ar[j]}
    end
    ar
  end
  
  def selection_sort
    ar = dup
    0.upto(n = ar.size - 1) do |i|
      min_idx = i
      (i + 1).upto(n) {|j| min_idx = j if ar[j] < ar[min_idx]}
      ar[i], ar[min_idx] = ar[min_idx], ar[i]
    end
    ar
  end
  
  def insertion_sort
    ar = dup
    1.upto(ar.size - 1) do |i|
      j = i
      while j > 0 and ar[j - 1] > ar[j]
	ar[j], ar[j - 1] = ar[j - 1], ar[j]
	j -= 1
      end
    end
    ar
  end
end

p [16, 14, 10, 8, 7, 9, 3, 2, 4, 1].insertion_sort
#=>[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

過去記事：
バブルソート - Camera Obscura
挿入ソート - Camera Obscura