Skip to content

Instantly share code, notes, and snippets.

@komasaru
Last active April 22, 2018 02:52
Show Gist options
  • Save komasaru/9969731 to your computer and use it in GitHub Desktop.
Save komasaru/9969731 to your computer and use it in GitHub Desktop.
Ruby script to test sorting algorithms.
#! /usr/local/bin/ruby
# **************************************
# ソート処理各種テスト
# **************************************
#
class SortTest
N = 100 # データ個数
M = 10000 # 値 MAX ( M 未満 )
L = 10000 # ソート試行回数
def initialize
# ヒープに追加する要素の配列を生成
@base = Array.new
N.times { |i| @base << Random.rand(N) + 1 }
# 乱数の種を毎回同じ値で初期化するなら以下2行のように。
#prng = Random.new(1234)
#N.times { |i| @base << prng.rand(N) + 1 }
# ベース配列出力
display_base
# 処理用配列
@a = Array.new # ソート処理用
@h = Array.new # ヒープ用
end
def exec
# 基本交換法(バブル・ソート)
printf("%-22s", "1 : Bubble Sort")
sort_bubble
# 基本選択法(直接選択法)
printf("%-22s", "2 : Selection Sort")
sort_selection
# 基本挿入法
printf("%-22s", "3 : Insertion Sort")
sort_insertion
# 改良交換法(クイック・ソート)
printf("%-22s", "4 : Quick Sort")
sort_quick
# 改良選択法(ヒープ・ソート)(上方移動)
printf("%-22s", "5-1: Heap Sort(Up)")
sort_heap_up
# 改良選択法(ヒープ・ソート)(下方移動)
printf("%-22s", "5-2: Heap Sort(Down)")
sort_heap_down
# 改良挿入法(シェル・ソート)
printf("%-22s", "6 : Shell Sort")
sort_shell
rescue => e
raise
end
private
# 基本交換法(バブル・ソート)
def sort_bubble
# 処理開始時刻
t1 = Time.now
# 指定回数 LOOP
L.times do |l|
# 配列コピー
#@a = @base.clone
@a = Marshal.load(Marshal.dump(@base))
# ソート処理
0.upto(N - 2) do |i|
(N - 1).downto(i + 1) do |j|
@a[j - 1], @a[j] = @a[j], @a[j - 1] if @a[j] < @a[j - 1]
end
end
end
# 処理時間計算・結果出力
t2 = Time.now
display(0, @a, t2 - t1)
rescue => e
raise
end
# 基本選択法(直接選択法)
def sort_selection
# 処理開始時刻
t1 = Time.now
# 指定回数 LOOP
L.times do |l|
# 配列コピー
#@a = @base.clone
@a = Marshal.load(Marshal.dump(@base))
# ソート処理
0.upto(N - 2) do |i|
min, s = @a[i], i
(i + 1).upto(N - 1) do |j|
min, s = @a[j], j if @a[j] < min
end
@a[i], @a[s] = @a[s], @a[i]
end
end
# 処理時間計算・結果出力
t2 = Time.now
display(0, @a, t2 - t1)
rescue => e
raise
end
# 基本挿入法
def sort_insertion
# 処理開始時刻
t1 = Time.now
# 指定回数 LOOP
L.times do |l|
# 配列コピー
#@a = @base.clone
@a = Marshal.load(Marshal.dump(@base))
# ソート処理
1.upto(N - 1) do |i|
(i - 1).downto(0) do |j|
if @a[j] > @a[j + 1]
@a[j], @a[j + 1] = @a[j + 1], @a[j]
else
break
end
end
end
end
# 処理時間計算・結果出力
t2 = Time.now
display(0, @a, t2 - t1)
rescue => e
raise
end
# 改良交換法 (クイック・ソート)
def sort_quick
# 処理開始時刻
t1 = Time.now
# 指定回数 LOOP
L.times do |l|
# 配列コピー
#@a = @base.clone
@a = Marshal.load(Marshal.dump(@base))
# ソート処理
quick(0, N - 1)
end
# 処理時間計算・結果出力
t2 = Time.now
display(0, @a, t2 - t1)
rescue => e
raise
end
# 改良選択法 (ヒープ・ソート)(上方移動)
def sort_heap_up
# 処理開始時刻
t1 = Time.now
# 指定回数 LOOP
L.times do |l|
# 初期ヒープ作成(上方移動)
generate_heap_up
# ソート処理
n, m = N, N # データ個数、n の保存
while n > 1
@h[1], @h[n] = @h[n], @h[1]
n -= 1 # 木の終端切り離し
p = 1; s = 2 * p
while s <= n
s += 1 if s < n && @h[s + 1] > @h[s]
break if @h[p] >= @h[s]
@h[p], @h[s] = @h[s], @h[p]
p = s; s = 2 * p
end
end
end
# 処理時間計算・結果出力
t2 = Time.now
display(1, @h, t2 - t1)
rescue => e
raise
end
# 改良選択法 (ヒープ・ソート)(下方移動)
def sort_heap_down
# 処理開始時刻
t1 = Time.now
# 指定回数 LOOP
L.times do |l|
# 元の配列を元の木としてコピー
1.upto(N) { |i| @h[i] = @base[i - 1] }
# 初期ヒープ作成(下方移動)
generate_heap_down
# ソート処理
n, m = N, N # データ個数, n の保存
while n > 1
@h[1], @h[n] = @h[n], @h[1]
n -= 1 # 木の終端切り離し
p = 1; s = 2 * p
while s <= n
s += 1 if s < n && @h[s + 1] > @h[s]
break if @h[p] >= @h[s]
@h[p], @h[s] = @h[s], @h[p]
p = s; s = 2 * p
end
end
end
# 処理時間計算・結果出力
t2 = Time.now
display(1, @h, t2 - t1)
rescue => e
raise
end
# 改良挿入法 (シェル・ソート)
def sort_shell
# 処理開始時刻
t1 = Time.now
# 指定回数 LOOP
L.times do |l|
# 配列コピー
#@a = @base.clone
@a = Marshal.load(Marshal.dump(@base))
# ソート処理
gap = N / 2
while gap > 0
0.upto(gap - 1) do |k|
i = k + gap
while i < N
j = i - gap
while j >= k
if @a[j] > @a[j + gap]
@a[j], @a[j + gap] = @a[j + gap], @a[j]
else
break
end
j -= gap
end
i += gap
end
end
gap /= 2
end
end
# 処理時間計算・結果出力
t2 = Time.now
display(0, @a, t2 - t1)
rescue => e
raise
end
# クイック・ソート用再帰関数
def quick(left, right)
return unless left < right
# 最左項を軸に. 軸より小さいグループ. 軸より大きいグループ.
s, i, j = @a[left], left, right + 1
loop do
i += 1; i += 1 while @a[i] && @a[i] < s
j -= 1; j -= 1 while @a[j] && @a[j] > s
break if i >= j
@a[i], @a[j] = @a[j], @a[i]
end
@a[left], @a[j] = @a[j], s # 軸を正しい位置に挿入
quick(left, j - 1) # 左部分列に対する再帰呼び出し
quick(j + 1, right) # 右部分列に対する再帰呼び出し
rescue => e
raise
end
# ヒープ・ソート用ヒープ生成(上方移動)関数
def generate_heap_up
1.upto(N) do |i|
# 元データ配列から1つヒープ要素として追加
@h[i] = @base[i - 1]
s = i # 追加の位置
p = s / 2 # 親要素の位置
while s >= 2 && @h[p] < @h[s]
@h[p], @h[s] = @h[s], @h[p]
s = p # 追加要素の位置
p = s / 2 # 親要素の位置
end
end
rescue => e
raise
end
# ヒープ・ソート用ヒープ生成(下方移動)関数
def generate_heap_down
n = N # データ個数
(n / 2).downto(1) do |i|
p = i # 親要素の位置
s = 2 * p # 左の子要素の位置
while s <= n
s += 1 if s < n && @h[s + 1] > @h[s] # 左右子要素の小さい方
break if @h[p] >= @h[s]
@h[p], @h[s] = @h[s], @h[p] # 交換
p = s # 親要素の位置
s = 2 * p # 左の子要素の位置
end
end
rescue => e
raise
end
# ベース配列出力
# param: 配列
def display_base
puts "#### Base Array"
0.upto(N - 1) do |i|
printf("%5d ", @base[i])
puts if (i + 1) % 10 == 0 || i == N - 1
end
puts
rescue => e
raise
end
# 結果出力
# param: 0(Heap 以外配列), 1(Heap 配列)
# 配列
# 経過時間
def display(k, ary, tt)
# ソート結果出力出力 ( 必要ならコメント解除 )
#puts
#k.upto(N - 1 + k) do |i|
# printf("%5d ", ary[i])
# puts if (i + 1 - k) % 10 == 0 || i == N - 1 + k
#end
# 経過時間出力
puts "Time: %6.2f sec." % tt
rescue => e
raise
end
end
if __FILE__ == $0
begin
SortTest.new.exec
rescue => e
$stderr.puts "[#{e.class}] #{e.message}"
e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment