Edited at

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

More than 3 years have passed since last update.

基礎から学ぶデータ構造とアルゴリズム』「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]


リンク