Anonymous user
Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 20:24, 12 March 2015
, 9 years agoAdded Ruby
(Added Ruby) |
|||
Line 1,373:
qsort - O(N*log(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}}==
| |||