Compare sorting algorithms' performance: Difference between revisions
Content added Content deleted
(Added Ruby) |
|||
Line 1,373: | Line 1,373: | ||
qsort - O(N*log(N)) |
qsort - O(N*log(N)) |
||
qsortranpart - O(N) ??? |
qsortranpart - O(N) ??? |
||
=={{header|Ruby}}== |
|||
<lang ruby>class Array |
|||
def radix_sort(base=10) # negative value is inapplicable. |
|||
ary = dup |
|||
rounds = (Math.log(ary.max)/Math.log(base)).ceil |
|||
rounds.times do |i| |
|||
buckets = Array.new(base){[]} |
|||
base_i = base**i |
|||
ary.each do |n| |
|||
digit = (n/base_i) % base |
|||
buckets[digit] << n |
|||
end |
|||
ary = buckets.flatten |
|||
end |
|||
ary |
|||
end |
|||
def quick_sort |
|||
return self if size <= 1 |
|||
pivot = sample |
|||
g = group_by{|x| x<=>pivot} |
|||
g.default = [] |
|||
g[-1].quick_sort + g[0] + g[1].quick_sort |
|||
end |
|||
def shell_sort |
|||
inc = size / 2 |
|||
while inc > 0 |
|||
(inc...size).each do |i| |
|||
value = self[i] |
|||
while i >= inc and self[i - inc] > value |
|||
self[i] = self[i - inc] |
|||
i -= inc |
|||
end |
|||
self[i] = value |
|||
end |
|||
inc = (inc == 2 ? 1 : (inc * 5.0 / 11).to_i) |
|||
end |
|||
self |
|||
end |
|||
def insertion_sort |
|||
(1...size).each do |i| |
|||
value = self[i] |
|||
j = i - 1 |
|||
while j >= 0 and self[j] > value |
|||
self[j+1] = self[j] |
|||
j -= 1 |
|||
end |
|||
self[j+1] = value |
|||
end |
|||
self |
|||
end |
|||
def bubble_sort |
|||
(1...size).each do |i| |
|||
(0...size-i).each do |j| |
|||
self[j], self[j+1] = self[j+1], self[j] if self[j] > self[j+1] |
|||
end |
|||
end |
|||
self |
|||
end |
|||
end |
|||
data_size = [1000, 10000, 100000, 1000000] |
|||
data = [] |
|||
data_size.each do |size| |
|||
ary = *1..size |
|||
data << [ [1]*size, ary, ary.shuffle, ary.reverse ] |
|||
end |
|||
data = data.transpose |
|||
data_type = ["set to all ones", "ascending sequence", "randomly shuffled", "descending sequence"] |
|||
print "Array size: " |
|||
puts data_size.map{|size| "%9d" % size}.join |
|||
data.each_with_index do |arys,i| |
|||
puts "\nData #{data_type[i]}:" |
|||
[:sort, :radix_sort, :quick_sort, :shell_sort, :insertion_sort, :bubble_sort].each do |m| |
|||
printf "%20s ", m |
|||
flag = true |
|||
arys.each do |ary| |
|||
if flag |
|||
t0 = Time.now |
|||
ary.dup.send(m) |
|||
printf " %7.3f", (t1 = Time.now - t0) |
|||
flag = false if t1 > 2 |
|||
else |
|||
print " --.---" |
|||
end |
|||
end |
|||
puts |
|||
end |
|||
end</lang> |
|||
Array#sort is a built-in method. |
|||
{{out}} |
|||
<pre> |
|||
Array size: 1000 10000 100000 1000000 |
|||
Data set to all ones: |
|||
sort 0.000 0.001 0.005 0.043 |
|||
radix_sort 0.000 0.002 0.012 0.084 |
|||
quick_sort 0.000 0.002 0.020 0.197 |
|||
shell_sort 0.002 0.018 0.234 2.897 |
|||
insertion_sort 0.000 0.002 0.020 0.198 |
|||
bubble_sort 0.064 6.328 --.--- --.--- |
|||
Data ascending sequence: |
|||
sort 0.000 0.000 0.002 0.020 |
|||
radix_sort 0.001 0.010 0.128 1.546 |
|||
quick_sort 0.004 0.058 0.521 5.996 |
|||
shell_sort 0.001 0.019 0.234 2.882 |
|||
insertion_sort 0.000 0.002 0.021 0.195 |
|||
bubble_sort 0.065 6.453 --.--- --.--- |
|||
Data randomly shuffled: |
|||
sort 0.000 0.002 0.024 0.263 |
|||
radix_sort 0.001 0.011 0.126 1.529 |
|||
quick_sort 0.004 0.081 0.522 6.192 |
|||
shell_sort 0.003 0.033 0.498 5.380 |
|||
insertion_sort 0.027 2.627 --.--- --.--- |
|||
bubble_sort 0.122 11.779 --.--- --.--- |
|||
Data descending sequence: |
|||
sort 0.000 0.001 0.001 0.021 |
|||
radix_sort 0.001 0.012 0.125 1.560 |
|||
quick_sort 0.004 0.061 0.522 5.873 |
|||
shell_sort 0.003 0.028 0.316 3.829 |
|||
insertion_sort 0.053 5.298 --.--- --.--- |
|||
bubble_sort 0.206 17.232 --.--- --.--- |
|||
</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |