Anonymous user
Talk:Sorting algorithms/Bubble sort: Difference between revisions
Undo revision 310324 by Charonn0 (talk) My mistake
(→An useful review: new section) |
|||
| (4 intermediate revisions by 4 users not shown) | |||
Line 93:
--[[User:PauliKL|PauliKL]] 16:22, 11 December 2008 (UTC)
==
My original [[CMake]] code was too slow, approaching [[O|O(n<sup>3</sup>)]]. A good bubble sort should be [[O|O(n<sup>2</sup>)]]. I benchmarked my CMake code with this [[Ruby]] script:
<lang ruby>require 'benchmark'
require 'tempfile'
def string(n)
(1..n).collect { rand(32000) }.join " "
end
def trial(string)
src = Tempfile.new 'cmake'
src.print <<EOF
# bubble_sort(var [value1 value2...]) sorts a list of integers.
function(bubble_sort var)
# !!!!! !!!!! !!!!! insert CMake code here !!!!! !!!!! !!!!!
endfunction(bubble_sort)
bubble_sort(result #{string})
EOF
src.flush
system "cmake", "-P", src.path
src.close
end
Benchmark.bm do |x|
a = string(100)
b = string(200)
c = string(300)
d = string(400)
x.report("100 integers") { trial(a) }
x.report("200 integers") { trial(b) }
x.report("300 integers") { trial(c) }
x.report("400 integers") { trial(d) }
end</lang>
[http://rosettacode.org/mw/index.php?title=Sorting_algorithms/Bubble_sort&oldid=121250#CMake The old code] used list operations against ''ARGN''. Because a list is a semicolon-delimited string (like "11;22;33;44;55;66"), these list operations might be O(n). Contrast other languages, where array operations are O(1).
Benchmark results for [http://rosettacode.org/mw/index.php?title=Sorting_algorithms/Bubble_sort&oldid=121250#CMake the old code]:
<pre>$ ruby bubble-old.rb
user system total real
100 integers 0.000000 0.000000 0.760000 ( 0.764968)
200 integers 0.000000 0.010000 4.860000 ( 4.875269)
300 integers 0.000000 0.000000 14.290000 ( 14.370998)
400 integers 0.000000 0.000000 31.700000 ( 31.647215)</pre>
* 100 integers: ''1 time''
* 200 integers: ''6 times slow''
* 300 integers: ''19 times slow''
* 400 integers: ''42 times slow'' '''(32 seconds)'''
The old code was slightly better than O(n<sup>3</sup>), but not much better. 6 was almost 8, 19 was almost 27, 42 was almost 64.
[http://rosettacode.org/mw/index.php?title=Sorting_algorithms/Bubble_sort&oldid=121403#CMake The new code] uses associative array operations against ''ARG1'' to ''ARG${last}''. The switch from a list to an associative array improves performance, but requires extra code at the end of bubble_sort() to convert the sorted associative array to a regular list.
Benchmark results for [http://rosettacode.org/mw/index.php?title=Sorting_algorithms/Bubble_sort&oldid=121403#CMake the new code]:
<pre>$ ruby bubble-new.rb
user system total real
100 integers 0.000000 0.000000 0.330000 ( 0.343380)
200 integers 0.000000 0.000000 1.220000 ( 1.220903)
300 integers 0.000000 0.000000 2.700000 ( 2.803828)
400 integers 0.000000 0.000000 4.910000 ( 5.047400)</pre>
* 100 integers: ''1 time''
* 200 integers: ''4 times slow''
* 300 integers: ''8 times slow''
* 400 integers: ''15 times slow'' '''(5 seconds)'''
The new code is very close to O(n<sup>2</sup>). The new bubble_sort() for CMake runs as fast as a bubble sort should run. --[[User:Kernigh|Kernigh]] 22:40, 24 September 2011 (UTC)
== "The elements must have a total order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers." ==
What exactly is this requirement? I thought that I had understood it, but when I've looked through some of the given solutions, it seems that many very powerful languages, such as every single language that has a name beginning with C, have only sorted an array of integers, implying that their language couldn't meet this requirement. Is there a misunderstanding somewhere? What examples was this requirement trying to encourage? --[[User:ReeceGoding|ReeceGoding]] ([[User talk:ReeceGoding|talk]]) 13:03, 2 August 2020 (UTC)
| |||