M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Ruby Programming

Ruby Junk Scripts

[ PrevPage | R u b y | NextPage ]

ソート

いろいろなソートプログラムです。

●参考文献

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

●テストプログラム

#
# testsort.rb : テストプログラム
#
require "sort.rb"

# 実行
def exec_sort(buff, func)
  begin
    total = 0.0
    3.times do
      a = buff.dup
      s = Time.now
      func.call(a)
      e = Time.now
      total += e - s
    end
    printf("%.3f ", total / 3)
  rescue
    print "------ "
  end
end

func_list1 = [
  proc {|buff| insert_sort(buff)},
  proc {|buff| buble_sort(buff)},
  proc {|buff| buble_sort1(buff)},
  proc {|buff| shaker_sort(buff)},
]

func_list = func_list1
NUM = 500

# 乱数データ
for i in 1 .. 4
  n = i * NUM
  buff = Array.new(n)
  buff.map! do rand(100000) end
  print n, ":"
  for func in func_list
    exec_sort(buff, func)
  end
  print "\n"
end

# 昇順データ
for i in 1 .. 4
  n = i * NUM
  buff = (0 ... n).to_a
  print n, ":"
  for func in func_list
    exec_sort(buff, func)
  end
  print "\n"
end

# 逆順データ
for i in 1 .. 4
  n = i * NUM
  buff = (0 ... n).to_a
  buff.reverse!
  print n, ":"
  for func in func_list
    exec_sort(buff, func)
  end
  print "\n"
end

# 山形データ
for i in 1 .. 4
  n = i * NUM
  buff = (0 ... n/2).to_a
  (n/2 - 1).downto(0) do |x|
    buff << x
  end
  print n, ":"
  for func in func_list
    exec_sort(buff, func)
  end
  print "\n"
end

ソート (1)

挿入ソート、バブルソート、シェーカーソートのプログラムです。

●プログラム

# 挿入ソート
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 buble_sort(buff)
  for i in 0 ... buff.size
    j = buff.size - 1
    while j > i
      if buff[j - 1] > buff[j]
        temp = buff[j]
        buff[j] = buff[j - 1]
        buff[j - 1] = temp
      end
      j -= 1
    end
  end
end

# バブルソート(改良版)
def buble_sort1(buff)
  k = buff.size - 1
  while k >= 0
    j = -1
    for i in 1 .. k
      if buff[i - 1] > buff[i]
        j = i - 1
        temp = buff[j]
        buff[j] = buff[i]
        buff[i] = temp
      end
    end
    k = j
  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]
        temp = buff[i]
        buff[i] = buff[i + 1]
        buff[i + 1] = temp
        j = i
      end
    end
    break if j == -1
    high = j
    j = -1
    i = high
    while i > low
      if buff[i - 1] > buff[i]
        temp = buff[i - 1]
        buff[i - 1] = buff[i]
        buff[i] = temp
        j = i
      end
      i -= 1
    end
    break if j == -1
    low = j
  end
end

●実行結果

  実行時間
  (単位;秒, Windows XP, Celeron 1.40 GHz, Ruby 1.8.3)

      乱数データ
      insert buble  buble1 shaker
---------------------------------
 500: 0.151  0.396  0.302  0.286 
1000: 0.573  1.583  1.198  1.141 
1500: 1.364  3.615  2.766  2.703 
2000: 2.365  6.370  4.891  4.677 

      昇順データ
      insert buble  buble1 shaker
---------------------------------
 500: 0.000  0.250  0.005  0.000 
1000: 0.000  1.010  0.005  0.000 
1500: 0.005  2.276  0.000  0.005 
2000: 0.005  4.042  0.005  0.000 

      逆順データ
      insert buble  buble1 shaker
---------------------------------
 500: 0.302  0.542  0.427  0.526 
1000: 1.198  2.177  1.714  2.062 
1500: 2.688  4.896  3.854  4.641 
2000: 4.792  8.703  6.849  8.261 

      山型データ
      insert buble  buble1 shaker
---------------------------------
 500: 0.151  0.396  0.307  0.297 
1000: 0.594  1.594  1.224  1.177 
1500: 1.344  3.589  2.760  2.656 
2000: 2.390  6.370  4.912  4.714 

ソート (2)

シェルソートとコームソートのプログラムです。

●プログラム

# シェルソート
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

# コームソート
# 参考文献 3. のプログラムを Ruby に移植しただけです。
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]
        temp = buff[i]
        buff[i] = buff[i + gap]
        buff[i + gap] = temp
        done = false
      end
    end
  end
end

# コームソート (2)
def comb_sort1(buff)
  gap = buff.size
  while gap > 1
    gap = (gap * 10) / 13
    gap = 11 if gap == 9 || gap == 10
    for i in 0 ... (buff.size - gap)
      if buff[i] > buff[i + gap]
        temp = buff[i]
        buff[i] = buff[i + gap]
        buff[i + gap] = temp
      end
    end
  end
  buble_sort1(buff)
end

# コームソート (3)
def comb_sort2(buff)
  gap = buff.size
  j = 0
  while (gap = (gap * 10) / 14) > 1
    gap = 11 if gap == 9 || gap == 10
    j += 1
    if j & 1
      for i in 0 ... (buff.size - gap)
        if buff[i] > buff[i + gap]
          temp = buff[i]
          buff[i] = buff[i + gap]
          buff[i + gap] = temp
        end
      end
    else
      i = buff.size - 1
      while i - gap >= 0
        if buff[i] < buff[i - gap]
          temp = buff[i]
          buff[i] = buff[i - gap]
          buff[i - gap] = temp
        end
        i -= 1
      end
    end
  end
  shaker_sort(buff)
end

●実行結果

  実行時間
  (単位;秒, Windows XP, Celeron 1.40 GHz, Ruby 1.8.3)

      乱数データ
      shell  comb   comb1  comb2
---------------------------------
1000: 0.042  0.042  0.042  0.037 
2000: 0.088  0.099  0.094  0.094 
3000: 0.146  0.151  0.151  0.156 
4000: 0.208  0.208  0.203  0.187 

      昇順データ
      shell  comb   comb1  comb2
---------------------------------
1000: 0.011  0.026  0.031  0.021 
2000: 0.031  0.063  0.068  0.052 
3000: 0.047  0.099  0.109  0.078 
4000: 0.073  0.141  0.151  0.109 

      逆順データ
      shell  comb   comb1  comb2
---------------------------------
1000: 0.026  0.037  0.031  0.026 
2000: 0.052  0.073  0.078  0.062 
3000: 0.094  0.120  0.114  0.099 
4000: 0.130  0.161  0.167  0.136 

      山型データ
      shell  comb   comb1  comb2
---------------------------------
1000: 0.026  0.036  0.036  0.026 
2000: 0.052  0.083  0.078  0.068 
3000: 0.083  0.125  0.125  0.104 
4000: 0.115  0.172  0.172  0.146 

ソート (3)

クイックソートのプログラムです。

●実行結果

# 再帰版
def quick_sort(buff, low, high)
  p = buff[(low + high)/2]
  i = low
  j = high
  loop do
    i += 1 while buff[i] < p
    j -= 1 while buff[j] > p
    break if i >= j
    temp = buff[i]
    buff[i] = buff[j]
    buff[j] = temp
    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 = buff[(low + high) / 2]
      # quick_sort2() は枢軸の選択に乱数を利用
      # p = buff[low + rand(high - low)]
      i = low
      j = high
      loop do
        i += 1 while buff[i] < p
        j -= 1 while buff[j] > p
        break if i >= j
        temp = buff[i]
        buff[i] = buff[j]
        buff[j] = temp
        i += 1
        j -= 1
      end
      if i - low > high - j
        low_stack << low
        high_stack << (i - 1)
        low = j + 1
      else
        low_stack << (j + 1)
        high_stack << high
        high = i - 1
      end
    end
    break if low_stack.empty?
    low = low_stack.pop
    high = high_stack.pop
  end
end

●実行結果

  実行時間
  (単位;秒, Windows XP, Celeron 1.40 GHz, Ruby 1.8.3)

      乱数データ
      quick  quick1 quick2
--------------------------
2000: 0.047  0.057  0.052 
4000: 0.104  0.120  0.125 
6000: 0.167  0.188  0.193 
8000: 0.240  0.265  0.255 

      昇順データ
      quick  quick1 quick2
--------------------------
2000: 0.026  0.021  0.031 
4000: 0.047  0.052  0.083 
6000: 0.083  0.078  0.109 
8000: 0.104  0.115  0.151 

      逆順データ
      quick  quick1 quick2
--------------------------
2000: 0.026  0.026  0.036 
4000: 0.057  0.057  0.078 
6000: 0.088  0.089  0.130 
8000: 0.115  0.130  0.167 

      山型データ
      quick  quick1 quick2
--------------------------
2000: 0.953  1.057  0.052 
4000: -----  4.167  0.120 
6000: -----  9.323  0.182 
8000: ----- 16.526  0.250 

ソート (4)

マージソート、ヒープソート、基数ソートのプログラムです。

●プログラム

# マージソート
# work は buff と同じ大きさ (半分にできる)
def merge_sort(buff, low, high, work)
  if high - low >= LIMIT
    insert_sort2(buff, low, high)
    return
  end
  mid = (low + high) / 2
  merge_sort(buff, low, mid, work)
  merge_sort(buff, mid + 1, high, work)
  for i in low .. mid
    work[i] = buff[i]
  end
  i = low
  j = mid + 1
  while i <= mid && j <= high
    if work[i] <= buff[j]
      buff[low] = work[i]
      i += 1
    else
      buff[low] = buff[j]
      j += 1
    end
    low += 1
  end
  while i <= mid
    buff[low] = work[i]
    i += 1
    low += 1
  end
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]
      temp = buff[n]
      buff[n] = buff[c]
      buff[c] = temp
      n = c
    end
    i -= 1
  end
  i = buff.size - 1
  while i > 0
    temp = buff[0]
    buff[0] = buff[i]
    buff[i] = temp
    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] = temp
      n = c
    end
    i -= 1
  end
end

# 基数ソート (32 bit 無符号整数専用)
def radix_sort(buff)
  count = Array.new(256)
  cumul = Array.new(256)
  work  = Array.new(buff.size)
  # 1 byte ずつ分布数えソート
  for i in 0 ... 4
    shift = i * 8
    count.fill(0)
    buff.each do |x|
      count[(x >> shift) & 0xff] += 1
    end
    sum = 0
    for x in 0 ... 256
      sum += count[x]
      cumul[x] = sum
    end
    x = buff.size - 1
    while x >= 0
      y = (buff[x] >> shift) & 0xff
      cumul[y] -= 1
      work[ cumul[y] ] = buff[x]
      x -= 1
    end
    temp = buff
    buff = work
    work = temp
  end
end

# 基数ソート (基数交換法1)
def radix_sort2(buff, low, high, n)
  return if low >= high || n == 0
  i = low
  j = high
  loop do
    i += 1 while i <= j && buff[i] & n == 0
    j -= 1 while i <= j && buff[j] & n > 0
    break if i > j
    temp = buff[i]
    buff[i] = buff[j]
    buff[j] = temp
    i += 1
    j -= 1
  end
  radix_sort2(buff, low, j, n >> 1)
  radix_sort2(buff, i, high, n >> 1)
end

# 基数ソート (基数交換法2)
def radix_sort3(buff, low, high, n)
  return if n == 0
  if high - low <= LIMIT
    insert_sort2(buff, low, high)
    return
  end
  i = low
  j = high
  loop do
    i += 1 while i <= j && buff[i] & n == 0
    j -= 1 while i <= j && buff[j] & n > 0
    break if i > j
    temp = buff[i]
    buff[i] = buff[j]
    buff[j] = temp
    i += 1
    j -= 1
  end
  radix_sort3(buff, low, j, n >> 1)
  radix_sort3(buff, i, high, n >> 1)
end

●実行結果

  実行時間
  (単位;秒, Windows XP, Celeron 1.40 GHz, Ruby 1.8.3)

      乱数データ
      quick2 merge  heap   radix  radxi2 radix3
-----------------------------------------------
2000: 0.057  0.078  0.130  0.047  0.130  0.104 
4000: 0.125  0.161  0.297  0.088  0.266  0.229 
6000: 0.188  0.265  0.474  0.130  0.406  0.349 
8000: 0.261  0.354  0.646  0.172  0.547  0.479 

      昇順データ
      quick2 merge  heap   radix  radix2 radix3
-----------------------------------------------
2000: 0.031  0.047  0.141  0.047  0.120  0.104 
4000: 0.062  0.094  0.312  0.089  0.240  0.213 
6000: 0.109  0.151  0.490  0.135  0.365  0.313 
8000: 0.156  0.203  0.677  0.177  0.479  0.422 

      逆順データ
      quick2 merge  heap   radix  radix2 radix3
-----------------------------------------------
2000: 0.031  0.073  0.130  0.042  0.125  0.109 
4000: 0.078  0.156  0.281  0.088  0.245  0.219 
6000: 0.120  0.250  0.438  0.135  0.370  0.323 
8000: 0.167  0.339  0.609  0.177  0.489  0.432 


      山型データ
      quick2 merge  heap   radix  radix2 radix3
-----------------------------------------------
2000: 0.057  0.063  0.135  0.047  0.130  0.125 
4000: 0.120  0.125  0.302  0.089  0.260  0.255 
6000: 0.188  0.203  0.474  0.130  0.385  0.391 
8000: 0.245  0.282  0.656  0.172  0.521  0.521 

Multikey Quicksort

マルチキークイックソート (Multikey Quicksort) は 1997 年に Jon Bentley と Robert Sedgewick が発表した文字列のソートに適した高速なアルゴリズムです。マルチキークイックソートで文字列をソートする場合、普通のクイックソートと大きく異なる点が 2 つあります。ひとつは文字単位で比較を行うことです。文字列をソートする場合、一般的なソートは文字列単位で比較を行います。ところが、マルチキークイックソートは最初に 1 文字目を比較してソートを行い、ソートが完了しない場合(同じ値が複数ある場合)は、さらに 2 文字目を比較してソートを行う、というように先頭から順番に文字を比較してソートを行います。

もうひとつは区間の分け方です。普通のクイックソートは枢軸を基準にして、小さいデータと大きいデータの 2 つの区間に分割していくことでソートを行います。マルチキークイックソートは枢軸を基準にするところは同じですが、区間を 2 分割するのではなく、小さいデータ、枢軸と等しいデータ、大きいデータの 3 分割にするところが特徴です。このため、マルチキークイックソートは Ternary Quicksort とも呼ばれています。

たとえば、n 番目の文字を比較して区間を 3 分割したとしましょう。小さいデータと大きいデータの区間は n 番目の文字でソートを続行すればいいですね。これは普通のクイックソートと同じです。枢軸と等しいデータが複数ある場合、n 番目の文字ではソートが完了しないので、次は n + 1 番目の文字を比較してソートを行います。このように枢軸と等しいデータを集めることで、その区間は次の文字へ進めることができるわけです。

このアルゴリズムを疑似コードでプログラムすると、次のようになります。

# Multikey Quicksort の擬似コード

def multikey_quicksort(low, high, n)
  if 区間のデータ数が NUM 以下
    単純なソートアルゴリズムに切り替えてソート
  else
    n 番目の文字で枢軸を選択して low - high を 3 分割する
    (< : low - m1-1, = : m1 - m2-1, > : m2 - high)
    multikey-quicksort(low, m1 - 1, n) 
    if n 番目の文字 != 終端記号
      multikey-quicksort( m1, m2 - 1, n + 1 )
    end
    multikey-quick( m2, high, n )
  end
end

マルチキークイックソートは再帰呼び出しを使うと簡単にプログラムできます。区間を low と high で表し、比較する文字の位置を n で表します。区間のデータ数が一定の個数 (NUM) 以下になったら、単純なソートアルゴリズムに切り替えます。この方が少しだけ速くなります。

n 番目の文字で区間を 3 分割したら、multikey-quicksort を再帰呼び出しします。このとき、枢軸より小さい区間 (low - m1-1) と大きい区間 (m2 - high) は n 番目の文字でソートを続行します。等しい区間 (m1 - m2-1) は n + 1 番目の文字へ進めてソートを行います。もしも、等しい区間の文字 (枢軸) が終端文字であれば、文字列を最後まで比較したので再帰呼び出しは行いません。つまり、同じ文字列が複数個あるということです。

●参考文献

  1. Jon Bentley, Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings", Sorting and Searching Strings, 1977

●プログラム

文字列の比較関数 compare を用意して、クイックソートとマルチキークイックソートの実行速度を比較します。文字列の比較に時間がかかる場合はマルチキークイックソートの方が速いのですが、そうでない場合はクイックソートの方が速くなります。

#
# mqsort.rb : Multikey Quicksort
#
#            Copyright (C) 2006 Makoto Hiroi
#
LIMIT = 10

# 文字列の終端を nil で判定する
def nil.coerce(n)
  [n, -1]
end

def nil.-(n)
  -1 - n
end

# 文字列の比較
def compare(s1, s2, depth = 0)
  for x in depth .. s1.size
    r = s1[x] - s2[x]
    return r if r != 0
  end
  0
end

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

# クイックソート
def quick_sort(buff)
  low_stack = []
  high_stack = []
  low = 0
  high = buff.size - 1
  loop do
    loop do
      if high - low <= LIMIT
        insert_sort(buff, low, high)
        break
      end
      p = buff[low + rand(high - low)]
      i = low
      j = high
      loop do
        i += 1 while compare(buff[i], p) < 0
        j -= 1 while compare(buff[j], p) > 0
        break if i >= j
        temp = buff[i]
        buff[i] = buff[j]
        buff[j] = temp
        i += 1
        j -= 1
      end
      if i - low > high - j
        low_stack << low
        high_stack << (i - 1)
        low = j + 1
      else
        low_stack << (j + 1)
        high_stack << high
        high = i - 1
      end
    end
    break if low_stack.empty?
    low = low_stack.pop
    high = high_stack.pop
  end
end

# マルチキークイックソート
def mqsort(buff, low, high, depth)
  if high - low <= LIMIT
    insert_sort(buff, low, high, depth)
    return
  end
  p = buff[low + rand(high - low)][depth]
  # 最初は 4 分割
  # low - m1-1 (p) | m1 - j | i - m2 | m2+1 - high (p)
  i = m1 = low
  j = m2 = high
  while true
    while i <= j
      k = buff[i][depth] - p
      break if k > 0
      if k == 0
        temp = buff[i]
        buff[i] = buff[m1]
        buff[m1] = temp
        m1 += 1
      end
      i += 1
    end
    while i <= j
      k = buff[j][depth] - p
      break if k < 0
      if k == 0
        temp = buff[j]
        buff[j] = buff[m2]
        buff[m2] = temp
        m2 -= 1
      end
      j -= 1
    end
    break if i > j
    temp = buff[i]
    buff[i] = buff[j]
    buff[j] = temp
    i += 1
    j -= 1
  end
  # 枢軸と等しいデータを中央に集める
  k = if m1 - low < i - m1 then m1 - low else i - m1 end
  for l in 0 ... k
    temp = buff[low + l]
    buff[low + l] = buff[j - l]
    buff[j - l] = temp
  end
  m1 = low + (i - m1)
  k = if high - m2 < m2 - j then high - m2 else m2 - j end
  for l in 0 ... k
    temp = buff[high - l]
    buff[high - l] = buff[i + l]
    buff[i + l] = temp
  end
  m2 = high - (m2 - j) + 1
  # m1 - m2-1 が等しいデータ
  mqsort(buff, low, m1 - 1, depth)
  if buff[m1][depth]
    mqsort(buff, m1, m2 - 1, depth + 1)
  end
  mqsort(buff, m2, high, depth)
end


if __FILE__ == $0
  4.times do |i|
    n = 2000 * (i + 1)
    a = []
    n.times do
      a << rand(0xffffffff).to_s
    end
    print n, ": " 
    b = a.dup
    s = Time.now
    mqsort(b, 0, b.size - 1, 0)
    e = Time.now
    print e - s, " "
    
    c = a.dup
    s = Time.now
    quick_sort(c)
    e = Time.now
    print e - s, "\n"
    d = a.sort
    print "error\n" if b != d || c != d
  end
end

●実行例

      mqsort  quick
--------------------
2000: 0.125   0.344
4000: 0.297   0.750
6000: 0.422   1.250
8000: 0.563   1.782

Copyright (C) 2006 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]