Anonymous user
Talk:Sorting algorithms/Bubble sort: Difference between revisions
Undo revision 310324 by Charonn0 (talk) My mistake
(idea: lets implement both!) |
|||
| (9 intermediate revisions by 8 users not shown) | |||
Line 73:
:::Yes, that is an optimized version of Bubble Sort which reduces the worst case execution time to half. (I fixed the swap command in your code.) The correct un-optimized version of Bubble Sort is given in the pseudo code in the article. The first code in this thread is a poor implementation of Selection sort (not Insertion Sort as I said earlier). --[[User:PauliKL|PauliKL]] 16:08, 10 December 2008 (UTC)
::::About swap, I've just copy-pasted the code on top of this section, it was not my intention to give working code here, I was just showing a point. It does not matter, but... the first code in this thread is no more the first :) --[[User:ShinTakezou|ShinTakezou]] 00:28, 11 December 2008 (UTC)
: How about a compromise? We implement both optimized and unoptimized versions on some other tasks. Why not here? (From that paper on the history of Bubble Sort, it appears that both forms have been named Bubble Sort over time. Earlier names include ''sorting by exchange'', "exchange sorting", and ''shuttle sort''. It appears Ken Iverson of [[APL]] and [[J]] fame first coined ''Bubble Sort''.) --[[User:IanOsgood|IanOsgood]] 17:22, 10 December 2008 (UTC)
::It could be done, but I suppose it is up to implementors; I've not done the C implementation, but if I had, I would have done it using the optimized "form", disregarding the ''expensive'' "form". --[[User:ShinTakezou|ShinTakezou]] 00:28, 11 December 2008 (UTC)
:::I don't know if it is necessary to have two implementations that has so little difference. In practice, the optimized version only requires decrementing the upper limit of the inner loop on each iteration and setting the initial value at the beginning. However, I notice both versions have been used in the implementations. So it might be good idea at least to mention on each implementation whether it uses optimized or un-optimized algorithm. --[[User:PauliKL|PauliKL]] 15:42, 11 December 2008 (UTC)
== Never used? ==
In the algorithm description, there is sentence ''"Because of its abysmal O(n2) performance, it is never used anywhere else"''.
That is, of course, totally untrue. Since bubble sort is the simplest sorting algorithm, it is the best choice for situations where speed is not critical (e.g. when sorting only small datasets), and/or when code size is important. In addition, it is stable and requires no additional space for temporary storage.
Further, there is nothing abysmal about O(n<sup>2</sup>) performance. Many commonly used algorithms have the same performance (e.g. insertion sort, selection sort). Worst case performance of Bubble Sort is the same as that of the best implementations of QuickSort, i.e. O(n<sup>2</sup>), and much better than naive implementation of QuickSort (infinite time). And best case performance for Bubble sort is much better than that of QuickSort.
Of course, Insertion Sort is only slightly more complex than Bubble Sort, and it is somewhat faster, so it could be preferred.
--[[User:PauliKL|PauliKL]] 16:22, 11 December 2008 (UTC)
== CMake ==
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)
| |||