Talk:Sorting algorithms/Bubble sort: Difference between revisions

== CMake ==

My original [[CMake]] code was too slow, approaching [[O|O(n³)]]. A good bubble sort should be [[O|O(n²)]]. 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³), 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²). The new bubble_sort() for CMake runs as fast as a bubble sort should run. --[[User:Kernigh|Kernigh]] 22:40, 24 September 2011 (UTC)