バブルソート、選択ソート、挿入ソート

『基礎から学ぶデータ構造とアルゴリズム』「4.1 単純な整列アルゴリズム」の勉強メモです。自分なりに咀嚼したソート手順とサンプルコード（Ruby）をまとめています。

バブルソート

1. 配列の末尾から先頭に向かって隣り合う要素を比較する
2. 後ろの要素が前の要素よりも小さければ交換する
3. 1, 2を繰り返す

def bubble_sort(a)
  n = a.size
  0.upto(n - 2) do |i|
    (n - 1).downto(i + 1) do |j|
      if a[j] < a[j - 1]
        a[j], a[j - 1] = a[j - 1], a[j]
        p a
      end
    end
  end
end

bubble_sort [2, 5, 3, 1, 4, 6]

[2, 5, 1, 3, 4, 6]
[2, 1, 5, 3, 4, 6]
[1, 2, 5, 3, 4, 6]
[1, 2, 3, 5, 4, 6]
[1, 2, 3, 4, 5, 6]

選択ソート

1. i = 0, 1, ..., n - 2 について、a[i + 1] ～ a[n - 1] のうち最小の要素を探し、a[i] と交換する

def selection_sort(a)
  n = a.size
  0.upto(n - 2) do |i|
    min = i
    (i + 1).upto(n - 1) do |j|
      min = j if a[j] < a[min]
    end
    if i != min
      a[i], a[min] = a[min], a[i]
      p a
    end
  end
end

selection_sort [2, 5, 3, 1, 4, 6]

[1, 5, 3, 2, 4, 6]
[1, 2, 3, 5, 4, 6]
[1, 2, 3, 4, 5, 6]

挿入ソート

1. 先頭の要素を整列済みとする
2. 整列済み要素の次の要素を、整列済みの部分の適切な位置に挿入する
3. 要素がなくなるまで、2 を繰り返す

def insertion_sort(a)
  n = a.size
  1.upto(n - 1) do |j|
    temp = a[j]
    i = j
    while i > 0 && a[i - 1] > temp
      a[i] = a[i - 1]
      i -= 1
    end
    if a[i] != temp
      a[i] = temp
      p a
    end
  end
end

insertion_sort [2, 5, 3, 1, 4, 6]

[2, 3, 5, 1, 4, 6]
[1, 2, 3, 5, 4, 6]
[1, 2, 3, 4, 5, 6]

リンク

• シェルソート
• クイックソート
• マージソート