いろいろなソートプログラムです。アルゴリズムの詳しい説明は拙作のページや参考文献をお読みください。
リスト : テストプログラム # テストデータの生成 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
リスト : ソート (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
リスト : ソート (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
リスト : ソート (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
リスト : ヒープソート 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
リスト : マージソート # 改良版 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
# 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