お気楽 Ruby プログラミング入門

ソート

いろいろなソートプログラムです。アルゴリズムの詳しい説明は拙作のページや参考文献をお読みください。

• Algorithms with Python
• 整列 [1]
  バブルソート、挿入ソート、選択ソート、シェーカーソート、シェルソート、コムソート、クイックソート
• 整列 [2]
  ヒープソート、マージソート

●参考文献

1. 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
2. 近藤嘉雪, 『Ｃプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998
3. Motoyuki's Diary 2000/5/26(Fri)

●テストプログラム

リスト : テストプログラム

# テストデータの生成
def make_data(x)
  # x は生成するデータの個数
  # 乱数
  a = (1..x).to_a.shuffle
  # 昇順
  b = (1..x).to_a
  # 降順
  c = b.reverse
  # 山型
  d = (1..x/2).to_a + (1..x/2).to_a.reverse
  return a, b, c, d
end

# ソートのチェック
def check(buff)
  for i in 0 ... buff.size-1
    raise "sort error" if buff[i] > buff[i + 1]
  end
end

# 時間計測
def sort_test(nums, &fn)
  print "  個数 : 乱数  : 昇順  : 逆順  : 山型  \n"
  print "-------+-------+-------+-------+-------\n"
  for n in nums
    printf "%6d ", n
    for buff in make_data(n)
      s = Time.now
      fn.call(buff)
      e = Time.now
      check(buff)
      printf ": %.3f ", e - s
    end
    print "\n"
  end
end

●実行環境

Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz

●注意事項

プログラムの実行時間は M.Hiroi のコーディング、実行したマシン、使用するプログラミング言語 (またはコンパイラ) などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間は大きく左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。

●バブルソート, シェーカーソート

リスト : ソート (1)

# バブルソート
def buble_sort(buff)
  for i in 0 ... buff.size
    j = buff.size - 1
    while j > i
      if buff[j - 1] > buff[j]
        buff[j], buff[j - 1] = buff[j - 1], buff[j]
      end
      j -= 1
    end
  end
end

# シェーカーソート
def shaker_sort(buff)
  low = 0
  high = buff.size - 1
  while low < high
    j = -1
    for i in low ... high
      if buff[i] > buff[i + 1]
        buff[i], buff[i + 1] = buff[i + 1], buff[i]
        j = i
      end
    end
    break if j == -1
    high = j
    j = -1
    i = high
    while i > low
      if buff[i - 1] > buff[i]
        buff[i - 1], buff[i] = buff[i], buff[i - 1]
        j = i
      end
      i -= 1
    end
    break if j == -1
    low = j
  end
end

    表 : バブルソート (単位 : 秒)

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
  1000 : 0.043 : 0.021 : 0.052 : 0.036
  2000 : 0.150 : 0.081 : 0.198 : 0.139
  4000 : 0.629 : 0.316 : 0.785 : 0.549
  8000 : 2.312 : 1.270 : 3.138 : 2.210

    表 : シェーカーソート (単位 : 秒)

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
  1000 : 0.039 : 0.000 : 0.063 : 0.043
  2000 : 0.152 : 0.000 : 0.241 : 0.144
  4000 : 0.578 : 0.000 : 0.963 : 0.554
  8000 : 2.320 : 0.001 : 3.837 : 2.231

• バブルソートは遅いソート
• 要素数を N とすると実行時間は O(N²) に比例する
• シェーカーソートはバブルソートの改良版
• 昇順のデータはとても速い (挿入ソートと同じ)
• それ以外はバブルソートとほぼ同じ (遅いソート)

●挿入ソート、選択ソート

リスト : ソート (2)

# 挿入ソート
def insert_sort(buff)
  for i in 1 ... buff.size
    temp = buff[i]
    j = i - 1
    while j >= 0 && temp < buff[j]
      buff[j + 1] = buff[j]
      j -= 1
    end
    buff[j + 1] = temp
  end
end

# 選択ソート
def select_sort(buff)
  for i in 0 ... buff.size-1
    m = i
    for j in i+1 ... buff.size
      m = j if buff[j] < buff[m]
    end
    buff[i], buff[m] = buff[m], buff[i]
  end
end

    表 : 挿入ソート (単位 : 秒)

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
  1000 : 0.017 : 0.000 : 0.030 : 0.015
  2000 : 0.062 : 0.000 : 0.143 : 0.075
  4000 : 0.269 : 0.001 : 0.477 : 0.230
  8000 : 0.903 : 0.001 : 1.826 : 0.914

    表 : 選択ソート (単位 : 秒)

       : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
  1000 : 0.042 : 0.036 : 0.039 : 0.038
  2000 : 0.142 : 0.144 : 0.147 : 0.145
  4000 : 0.560 : 0.561 : 0.580 : 0.570
  8000 : 2.243 : 2.248 : 2.367 : 2.268

• 挿入ソートと選択ソートは遅いソート
• 要素数を N とすると実行時間は O(N²) に比例する
• 昇順データは挿入ソートがとても速い
• データの比較回数は挿入ソートのほうが少なくなる (平均すると約半分になる)
• データの移動回数は選択ソートの方が少なくなる
• 今回のプログラムでは選択ソートの方が速くなった

●シェルソート, コームソート

リスト : ソート (3)

# シェルソート
def shell_sort(buff)
  gap = 1
  gap = gap * 3 + 1 while gap < buff.size / 9
  while gap > 0
    for i in gap ... buff.size
      temp = buff[i]
      j = i - gap
      while j >= 0 && temp < buff[j]
        buff[j + gap] = buff[j]
        j -= gap
      end
      buff[j + gap] = temp
    end
    gap /= 3
  end
end

# コームソート
def comb_sort(buff)
  gap = buff.size
  done = false
  while gap > 1 || (not done)
    gap = (gap * 10) / 13
    gap = 1 if gap == 0
    gap = 11 if gap == 9 || gap == 10
    done = true
    for i in 0 ... (buff.size - gap)
      if buff[i] > buff[i + gap]
        buff[i], buff[i + gap] = buff[i + gap], buff[i]
        done = false
      end
    end
  end
end

    表 : シェルソート (単位 : 秒)

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
 10000 : 0.023 : 0.009 : 0.013 : 0.013
 20000 : 0.046 : 0.019 : 0.028 : 0.027
 40000 : 0.103 : 0.040 : 0.058 : 0.054
 80000 : 0.226 : 0.084 : 0.123 : 0.113
160000 : 0.553 : 0.183 : 0.256 : 0.243
320000 : 1.164 : 0.399 : 0.535 : 0.516

    表 : コームソート (単位 : 秒)

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
 10000 : 0.030 : 0.021 : 0.026 : 0.024
 20000 : 0.063 : 0.044 : 0.050 : 0.051
 40000 : 0.137 : 0.101 : 0.109 : 0.116
 80000 : 0.276 : 0.212 : 0.233 : 0.244
160000 : 0.617 : 0.449 : 0.491 : 0.505
320000 : 1.288 : 0.962 : 1.040 : 1.085

• シェルソートは gap を奇数になるようにすると O(N^1.5) になる
• Knuth 先生の数列で gap を更新すると O(N^1.25) になる
• 今回のプログラムは Knuth 先生の方法を採用
• コームソートは 参考文献 3 のプログラムを Ruby に移植しただけ
• バブルソートや挿入ソートよりも速いが、シェルソートよりも少し遅くなった

●クイックソート

リスト : ソート (4)

# 中央値を返す
def median3(a, b, c)
  if a > b
    b > c ? b : (a < c ? a : c)
  else
    b < c ? b : (a < c ? c : a)
  end
end

#
# 再帰版
#
def quick_sort(buff, low, high)
  p = median3(buff[low], buff[(low + high) / 2], buff[high])
  i, j = low, high
  loop do
    i += 1 while buff[i] < p
    j -= 1 while buff[j] > p
    break if i >= j
    buff[i], buff[j] = buff[j], buff[i]
    i += 1
    j -= 1
  end
  quick_sort(buff, low, i - 1) if i - low > 1
  quick_sort(buff, j + 1, high) if high - j > 1
end

#
# 非再帰版
#

# 定数
LIMIT = 10

# 挿入ソート
def insert_sort2(buff, low, high)
  for i in low+1 .. high
    temp = buff[i]
    j = i - 1
    while j >= low && temp < buff[j]
      buff[j + 1] = buff[j]
      j -= 1
    end
    buff[j + 1] = temp
  end
end

def quick_sort1(buff)
  low_stack = []
  high_stack = []
  low = 0
  high = buff.size - 1
  loop do
    loop do
      if high - low <= LIMIT
        insert_sort2(buff, low, high)
        break
      end
      p = median3(buff[low], buff[(low + high) / 2], buff[high])
      i = low
      j = high
      loop do
        i += 1 while buff[i] < p
        j -= 1 while buff[j] > p
        break if i >= j
        buff[i], buff[j] = buff[j], buff[i]
        i += 1
        j -= 1
      end
      if i - low > high - j
        low_stack.push low
        high_stack.push(i - 1)
        low = j + 1
      else
        low_stack.push(j + 1)
        high_stack.push high
        high = i - 1
      end
    end
    break if low_stack.empty?
    low = low_stack.pop
    high = high_stack.pop
  end
end

    表 : クイックソート (単位 : 秒)
            [再帰版]

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
 10000 : 0.014 : 0.005 : 0.006 : 0.017
 20000 : 0.027 : 0.012 : 0.013 : 0.037
 40000 : 0.055 : 0.022 : 0.025 : 0.081
 80000 : 0.112 : 0.046 : 0.051 : 0.171
160000 : 0.232 : 0.094 : 0.106 : 0.365
320000 : 0.487 : 0.200 : 0.212 : 0.794

    表 : クイックソート (単位 : 秒)
           [非再帰版]

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
 10000 : 0.011 : 0.005 : 0.005 : 0.017
 20000 : 0.023 : 0.010 : 0.010 : 0.036
 40000 : 0.048 : 0.020 : 0.023 : 0.075
 80000 : 0.102 : 0.042 : 0.047 : 0.167
160000 : 0.213 : 0.088 : 0.095 : 0.353
320000 : 0.447 : 0.178 : 0.198 : 0.772

• クイックソートは O(N*log₂N) に比例する高速なソート
• データによっては O(N²) に比例する遅いソートになる
• 区間の中央に位置する要素を枢軸とすると、山型データが最悪となる
• 再帰版はスタックオーバーフローする
• 非再帰版はとても遅くなる
• 今回は枢軸の選択に median-of-3 を採用しているので山型データでも大丈夫
• median-of-3 は 3 つの要素の中から中央値を枢軸とする方法
• 9 つの要素の中から中央値を枢軸とする median-of-9 という方法もある
• 再帰版よりも非再帰版のほうがちょっとだけ高速になった

●ヒープソート, マージソート

リスト : ヒープソート

def heap_sort(buff)
  i = buff.size / 2 - 1
  while i >= 0
    n = i
    loop do
      c = 2 * n + 1
      break if c >= buff.size
      if c + 1 < buff.size
        c += 1 if buff[c] < buff[c + 1]
      end
      break if buff[n] >= buff[c]
      buff[n], buff[c] = buff[c], buff[n]
      n = c
    end
    i -= 1
  end
  i = buff.size - 1
  while i > 0
    buff[0], buff[i] = buff[i], buff[0]
    n = 0
    loop do
      c = 2 * n + 1
      break if c >= i
      if c + 1 < i
        c += 1 if buff[c] < buff[c + 1]
      end
      break if buff[n] >= buff[c]
      temp = buff[n]
      buff[n], buff[c] = buff[c], buff[n]
      n = c
    end
    i -= 1
  end
end

    表 : ヒープソート (単位 : 秒)

  個数 : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
 10000 : 0.033 : 0.029 : 0.031 : 0.029
 20000 : 0.061 : 0.061 : 0.056 : 0.060
 40000 : 0.127 : 0.134 : 0.120 : 0.125
 80000 : 0.270 : 0.282 : 0.256 : 0.264
160000 : 0.571 : 0.575 : 0.534 : 0.571
320000 : 1.228 : 1.285 : 1.128 : 1.183

• ヒープソートは O(N*log₂N) に比例する高速なソート
• 実際にソートするとクイックソートのほうが速くなる
• ヒープソートの速度はクイックソートの半分くらい
• クイックソートとは違い、どのようなデータでもそこそこの速度でソートできる

リスト : マージソート

# 改良版
def merge_sort(a, b, low, high)
  if high - low <= LIMIT
    insert_sort2(b, low, high)
  else
    mid = (low + high) / 2
    merge_sort(b, a, low, mid)
    merge_sort(b, a, mid + 1, high)
    i = low
    j = mid + 1
    k = low
    while i <= mid and j <= high
      if a[i] <= a[j]
        b[k] = a[i]
        i += 1
      else
        b[k] = a[j]
        j += 1
      end
      k += 1
    end
    while i <= mid
      b[k] = a[i]
      k += 1
      i += 1
    end
    while j <= high
      b[k] = a[j]
      k += 1
      j += 1
    end
  end
end

def msort(buff)
  work = buff.dup
  merge_sort(work, buff, 0, buff.size - 1)
end

    表 : マージソート (単位 : 秒)

       : 乱数  : 昇順  : 逆順  : 山型
-------+-------+-------+-------+-------
 10000 : 0.012 : 0.008 : 0.012 : 0.009
 20000 : 0.026 : 0.017 : 0.024 : 0.020
 40000 : 0.054 : 0.035 : 0.047 : 0.041
 80000 : 0.112 : 0.076 : 0.095 : 0.088
160000 : 0.238 : 0.162 : 0.200 : 0.184
320000 : 0.524 : 0.343 : 0.419 : 0.386

• マージソートは O(N*log₂N) に比例する高速なソート
• 実際にソートするとクイックソートのほうが速くなる
• クイックソートとは違い、どのようなデータでもそこそこの速度でソートできる
• ただし、マージソートは作業領域 (work) が必要になる
• work のサイズは N / 2 で十分だが、今回はサイズ N の work を用意している
• 最初に buff を work にコピーしておいて、再帰のたびに buff と work を交互に入れ換える
• これでマージソートの実行速度を改善することができる

●プログラムリスト

# coding: utf-8
#
# sort.rb : ソート
#
#           Copyright (C) 2023 Makoto Hiroi
#

# テストデータの生成
def make_data(x)
  # x は生成するデータの個数
  # 乱数
  a = (1..x).to_a.shuffle
  # 昇順
  b = (1..x).to_a
  # 降順
  c = b.reverse
  # 山型
  d = (1..x/2).to_a + (1..x/2).to_a.reverse
  return a, b, c, d
end

# ソートのチェック
def check(buff)
  for i in 0 ... buff.size-1
    raise "sort error" if buff[i] > buff[i + 1]
  end
end

# 時間計測
def sort_test(nums, &fn)
  print "  個数 : 乱数  : 昇順  : 逆順  : 山型  \n"
  print "-------+-------+-------+-------+-------\n"
  for n in nums
    printf "%6d ", n
    for buff in make_data(n)
      s = Time.now
      fn.call(buff)
      e = Time.now
      check(buff)
      printf ": %.3f ", e - s
    end
    print "\n"
  end
end

#
# バブルソート
#
def buble_sort(buff)
  for i in 0 ... buff.size
    j = buff.size - 1
    while j > i
      if buff[j - 1] > buff[j]
        buff[j], buff[j - 1] = buff[j - 1], buff[j]
      end
      j -= 1
    end
  end
end

#
# 挿入ソート
#
def insert_sort(buff)
  for i in 1 ... buff.size
    temp = buff[i]
    j = i - 1
    while j >= 0 && temp < buff[j]
      buff[j + 1] = buff[j]
      j -= 1
    end
    buff[j + 1] = temp
  end
end

#
# 選択ソート
#
def select_sort(buff)
  for i in 0 ... buff.size-1
    m = i
    for j in i+1 ... buff.size
      m = j if buff[j] < buff[m]
    end
    buff[i], buff[m] = buff[m], buff[i]
  end
end

#
# シェーカーソート
#
def shaker_sort(buff)
  low = 0
  high = buff.size - 1
  while low < high
    j = -1
    for i in low ... high
      if buff[i] > buff[i + 1]
        buff[i], buff[i + 1] = buff[i + 1], buff[i]
        j = i
      end
    end
    break if j == -1
    high = j
    j = -1
    i = high
    while i > low
      if buff[i - 1] > buff[i]
        buff[i - 1], buff[i] = buff[i], buff[i - 1]
        j = i
      end
      i -= 1
    end
    break if j == -1
    low = j
  end
end

#
# シェルソート
#
def shell_sort(buff)
  gap = 1
  gap = gap * 3 + 1 while gap < buff.size / 9
  while gap > 0
    for i in gap ... buff.size
      temp = buff[i]
      j = i - gap
      while j >= 0 && temp < buff[j]
        buff[j + gap] = buff[j]
        j -= gap
      end
      buff[j + gap] = temp
    end
    gap /= 3
  end
end

#
# コームソート
#
def comb_sort(buff)
  gap = buff.size
  done = false
  while gap > 1 || (not done)
    gap = (gap * 10) / 13
    gap = 1 if gap == 0
    gap = 11 if gap == 9 || gap == 10
    done = true
    for i in 0 ... (buff.size - gap)
      if buff[i] > buff[i + gap]
        buff[i], buff[i + gap] = buff[i + gap], buff[i]
        done = false
      end
    end
  end
end

#
# クイックソート
#

# 中央値を返す
def median3(a, b, c)
  if a > b
    b > c ? b : (a < c ? a : c)
  else
    b < c ? b : (a < c ? c : a)
  end
end

# 再帰版
def quick_sort(buff, low, high)
  p = median3(buff[low], buff[(low + high) / 2], buff[high])
  i, j = low, high
  loop do
    i += 1 while buff[i] < p
    j -= 1 while buff[j] > p
    break if i >= j
    buff[i], buff[j] = buff[j], buff[i]
    i += 1
    j -= 1
  end
  quick_sort(buff, low, i - 1) if i - low > 1
  quick_sort(buff, j + 1, high) if high - j > 1
end

# 定数
LIMIT = 10

# 挿入ソート
def insert_sort2(buff, low, high)
  for i in low+1 .. high
    temp = buff[i]
    j = i - 1
    while j >= low && temp < buff[j]
      buff[j + 1] = buff[j]
      j -= 1
    end
    buff[j + 1] = temp
  end
end

# 非再帰版
def quick_sort1(buff)
  low_stack = []
  high_stack = []
  low = 0
  high = buff.size - 1
  loop do
    loop do
      if high - low <= LIMIT
        insert_sort2(buff, low, high)
        break
      end
      p = median3(buff[low], buff[(low + high) / 2], buff[high])
      i = low
      j = high
      loop do
        i += 1 while buff[i] < p
        j -= 1 while buff[j] > p
        break if i >= j
        buff[i], buff[j] = buff[j], buff[i]
        i += 1
        j -= 1
      end
      if i - low > high - j
        low_stack.push low
        high_stack.push(i - 1)
        low = j + 1
      else
        low_stack.push(j + 1)
        high_stack.push high
        high = i - 1
      end
    end
    break if low_stack.empty?
    low = low_stack.pop
    high = high_stack.pop
  end
end

#
# マージソート
#

# 改良版
def merge_sort(a, b, low, high)
  if high - low <= LIMIT
    insert_sort2(b, low, high)
  else
    mid = (low + high) / 2
    merge_sort(b, a, low, mid)
    merge_sort(b, a, mid + 1, high)
    i = low
    j = mid + 1
    k = low
    while i <= mid and j <= high
      if a[i] <= a[j]
        b[k] = a[i]
        i += 1
      else
        b[k] = a[j]
        j += 1
      end
      k += 1
    end
    while i <= mid
      b[k] = a[i]
      k += 1
      i += 1
    end
    while j <= high
      b[k] = a[j]
      k += 1
      j += 1
    end
  end
end

def msort(buff)
  work = buff.dup
  merge_sort(work, buff, 0, buff.size - 1)
end

#
# ヒープソート
#
def heap_sort(buff)
  i = buff.size / 2 - 1
  while i >= 0
    n = i
    loop do
      c = 2 * n + 1
      break if c >= buff.size
      if c + 1 < buff.size
        c += 1 if buff[c] < buff[c + 1]
      end
      break if buff[n] >= buff[c]
      buff[n], buff[c] = buff[c], buff[n]
      n = c
    end
    i -= 1
  end
  i = buff.size - 1
  while i > 0
    buff[0], buff[i] = buff[i], buff[0]
    n = 0
    loop do
      c = 2 * n + 1
      break if c >= i
      if c + 1 < i
        c += 1 if buff[c] < buff[c + 1]
      end
      break if buff[n] >= buff[c]
      temp = buff[n]
      buff[n], buff[c] = buff[c], buff[n]
      n = c
    end
    i -= 1
  end
end