Anonymous user
Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 19:29, 24 April 2009
, 15 years agoadd Tcl, partial solution
m (clicke save one seconds too fast... (C comes before P)) |
(add Tcl, partial solution) |
||
Line 423:
qsort - O(N*log(N))
qsortranpart - O(N) ???
=={{header|Tcl}}==
This solution does not address the plotting requirement of the task.
<code>lsort</code> is Tcl's built-in sorting command.
<lang tcl># list creation procedures
proc ones n {
lrepeat $n 1
}
proc reversed n {
while {[incr n -1] >= 0} {
lappend result $n
}
return $result
}
proc random n {
for {set i 0} {$i < $n} {incr i} {
lappend result [expr {int($n * rand())}]
}
return $result
}
set algorithms {lsort quicksort shellsort insertionsort bubblesort}
set sizes {1 10 100 1000 10000 100000}
set types {ones reversed random}
# create some lists to be used by all sorting algorithms
array set lists {}
foreach size $sizes {
foreach type $types {
set lists($type,$size) [$type $size]
}
}
set runs 10
# header
fconfigure stdout -buffering none
puts -nonewline [format "%-16s" "list length:"]
foreach size $sizes {
puts -nonewline [format " %10d" $size]
}
puts ""
# perform the sort timings and output results
foreach type $types {
puts "\nlist type: $type"
foreach algo $algorithms {
set errs [list]
$algo {} ;# call it once to ensure it's compiled
puts -nonewline [format " %-13s" $algo]
foreach size $sizes {
# some implementations are just too slow
if {$type ne "ones" && (
($algo eq "insertionsort" && $size > 10000) ||
($algo eq "bubblesort" && $size > 1000))
} {
set time "skipped"
} else {
# OK, do it
if {[catch {time [list $algo $lists($type,$size)] $runs} result] != 0} {
set time -1
lappend errs $result
} else {
set time [lindex [split $result] 0]
}
}
puts -nonewline [format " %10s" $time]
}
puts ""
if {[llength $errs] > 0} {
puts [format " %s" [join $errs "\n "]]
}
}
}
puts "\ntimes in microseconds, average of $runs runs"</lang>
outputs
<pre>list length: 1 10 100 1000 10000 100000
list type: ones
lsort 0.8 1.3 8.7 99.0 1007.4 12171.6
quicksort 1.1 8.1 52.7 398.7 3758.3 36828.4
shellsort 1.3 20.7 257.8 4209.7 58185.7 749289.4
insertionsort 1.1 6.5 62.3 638.2 5617.0 53863.3
bubblesort 2.7 7.8 38.6 324.2 3463.3 34478.5
list type: reversed
lsort 1.9 1.5 12.3 120.8 1565.0 21087.8
quicksort 2.5 41.1 534.2 6435.8 79947.2 981884.1
shellsort 3.1 36.6 453.5 6694.2 93966.8 1234147.3
insertionsort 2.0 24.9 1553.5 153679.5 15814539.4 skipped
bubblesort 4.0 485.8 47525.8 4838366.7 skipped skipped
list type: random
lsort 1.8 1.8 18.1 243.5 3237.4 61951.7
quicksort 1.3 30.7 462.8 5631.2 74675.1 945864.0
shellsort 3.1 27.9 608.7 9412.5 141413.7 2334003.6
insertionsort 2.5 13.4 848.3 78158.5 7836658.9 skipped
bubblesort 4.0 160.5 24189.7 2458080.7 skipped skipped
times in microseconds, average of 10 runs</pre>
| |||