huntley@copper.ucs.indiana.edu (Haydn Huntley) (09/30/90)
Mac IIcx, sorting 1024 long integers, compiled with Think C 4.0.1
median FMR quick sort -- random list -- 0.241 secs -- 10455 compares
median FMR quick sort -- semi-random list -- 0.231 secs -- 10255 compares
median FMR quick sort -- ordered list -- 0.118 secs -- 8293 compares
median FMR quick sort -- reverse list -- 0.218 secs -- 10082 compares
median FMR quick sort -- almost sorted list -- 0.198 secs -- 9417 compares
BEST CASE -- 0.118 secs -- 8293 compares
WORST CASE -- 0.241 secs -- 10455 compares
AVERAGE -- 0.201 secs -- 9700 compares
median FRR quick sort -- random list -- 0.245 secs -- 10913 compares
median FRR quick sort -- semi-random list -- 0.235 secs -- 10603 compares
median FRR quick sort -- ordered list -- 0.139 secs -- 9790 compares
median FRR quick sort -- reverse list -- 0.210 secs -- 10361 compares
median FRR quick sort -- almost sorted list -- 0.206 secs -- 10467 compares
BEST CASE -- 0.139 secs -- 9790 compares
WORST CASE -- 0.245 secs -- 10913 compares
AVERAGE -- 0.207 secs -- 10426 compares
median MRR quick sort -- random list -- 0.262 secs -- 11458 compares
median MRR quick sort -- semi-random list -- 0.236 secs -- 10324 compares
median MRR quick sort -- ordered list -- 0.136 secs -- 8870 compares
median MRR quick sort -- reverse list -- 0.221 secs -- 9752 compares
median MRR quick sort -- almost sorted list -- 0.194 secs -- 9408 compares
BEST CASE -- 0.136 secs -- 8870 compares
WORST CASE -- 0.262 secs -- 11458 compares
AVERAGE -- 0.210 secs -- 9962 compares
random quick sort -- random list -- 0.265 secs -- 11759 compares
random quick sort -- semi-random list -- 0.249 secs -- 11343 compares
random quick sort -- ordered list -- 0.132 secs -- 9528 compares
random quick sort -- reverse list -- 0.231 secs -- 10260 compares
random quick sort -- almost sorted list -- 0.203 secs -- 10725 compares
BEST CASE -- 0.132 secs -- 9528 compares
WORST CASE -- 0.265 secs -- 11759 compares
AVERAGE -- 0.216 secs -- 10723 compares
fastQsort -- random list -- 0.267 secs -- 11661 compares
fastQsort -- semi-random list -- 0.250 secs -- 11047 compares
fastQsort -- ordered list -- 0.226 secs -- 10730 compares
fastQsort -- reverse list -- 0.244 secs -- 11309 compares
fastQsort -- almost sorted list -- 0.231 secs -- 11038 compares
BEST CASE -- 0.226 secs -- 10730 compares
WORST CASE -- 0.267 secs -- 11661 compares
AVERAGE -- 0.244 secs -- 11157 compares
median RRR quick sort -- random list -- 0.268 secs -- 11094 compares
median RRR quick sort -- semi-random list -- 0.258 secs -- 10882 compares
median RRR quick sort -- ordered list -- 0.132 secs -- 8841 compares
median RRR quick sort -- reverse list -- 0.216 secs -- 9755 compares
median RRR quick sort -- almost sorted list -- 0.197 secs -- 9400 compares
BEST CASE -- 0.132 secs -- 8841 compares
WORST CASE -- 0.268 secs -- 11094 compares
AVERAGE -- 0.214 secs -- 9994 compares
modified THINK qsort -- random list -- 0.272 secs -- 11734 compares
modified THINK qsort -- semi-random list -- 0.259 secs -- 11189 compares
modified THINK qsort -- ordered list -- 0.232 secs -- 10878 compares
modified THINK qsort -- reverse list -- 0.254 secs -- 11742 compares
modified THINK qsort -- almost sorted list -- 0.238 secs -- 11197 compares
BEST CASE -- 0.232 secs -- 10878 compares
WORST CASE -- 0.272 secs -- 11742 compares
AVERAGE -- 0.251 secs -- 11348 compares
shell sort -- random list -- 0.325 secs -- 13853 compares
shell sort -- semi-random list -- 0.317 secs -- 13854 compares
shell sort -- ordered list -- 0.083 secs -- 5601 compares
shell sort -- reverse list -- 0.199 secs -- 9175 compares
shell sort -- almost sorted list -- 0.223 secs -- 10649 compares
BEST CASE -- 0.083 secs -- 5601 compares
WORST CASE -- 0.325 secs -- 13854 compares
AVERAGE -- 0.229 secs -- 10626 compares
merge sort -- random list -- 0.389 secs -- 8974 compares
merge sort -- semi-random list -- 0.359 secs -- 8880 compares
merge sort -- ordered list -- 0.286 secs -- 5120 compares
merge sort -- reverse list -- 0.283 secs -- 5120 compares
merge sort -- almost sorted list -- 0.339 secs -- 7862 compares
BEST CASE -- 0.283 secs -- 5120 compares
WORST CASE -- 0.389 secs -- 8974 compares
AVERAGE -- 0.331 secs -- 7191 compares
Gish's heap sort -- random list -- 0.506 secs -- 17420 compares
Gish's heap sort -- semi-random list -- 0.504 secs -- 17549 compares
Gish's heap sort -- ordered list -- 0.526 secs -- 18060 compares
Gish's heap sort -- reverse list -- 0.466 secs -- 16407 compares
Gish's heap sort -- almost sorted list -- 0.523 secs -- 17962 compares
BEST CASE -- 0.466 secs -- 16407 compares
WORST CASE -- 0.526 secs -- 18060 compares
AVERAGE -- 0.505 secs -- 17479 compares
heap sort -- random list -- 0.624 secs -- 17420 compares
heap sort -- semi-random list -- 0.631 secs -- 17549 compares
heap sort -- ordered list -- 0.648 secs -- 18060 compares
heap sort -- reverse list -- 0.579 secs -- 16407 compares
heap sort -- almost sorted list -- 0.647 secs -- 17962 compares
BEST CASE -- 0.579 secs -- 16407 compares
WORST CASE -- 0.648 secs -- 18060 compares
AVERAGE -- 0.626 secs -- 17479 compares
median FML quick sort -- random list -- 0.239 secs -- 10506 compares
median FML quick sort -- semi-random list -- 0.219 secs -- 10054 compares
median FML quick sort -- ordered list -- 0.106 secs -- 7559 compares
median FML quick sort -- reverse list -- 1.182 secs -- 89054 compares
median FML quick sort -- almost sorted list -- 0.215 secs -- 12265 compares
BEST CASE -- 0.106 secs -- 7559 compares
WORST CASE -- 1.182 secs -- 89054 compares
AVERAGE -- 0.392 secs -- 25887 compares
naive quick sort -- random list -- 0.274 secs -- 12447 compares
naive quick sort -- semi-random list -- 0.260 secs -- 12095 compares
naive quick sort -- ordered list -- 6.006 secs -- 523098 compares
naive quick sort -- reverse list -- 6.584 secs -- 523197 compares
naive quick sort -- almost sorted list -- 0.311 secs -- 20180 compares
BEST CASE -- 0.260 secs -- 12095 compares
WORST CASE -- 6.584 secs -- 523197 compares
AVERAGE -- 2.687 secs -- 218203 compares
THINK's qsort -- random list -- 0.887 secs -- 13674 compares
THINK's qsort -- semi-random list -- 0.982 secs -- 15960 compares
THINK's qsort -- ordered list -- 29.502 secs -- 524799 compares
THINK's qsort -- reverse list -- 28.910 secs -- 524799 compares
THINK's qsort -- almost sorted list -- 2.906 secs -- 51698 compares
BEST CASE -- 0.887 secs -- 13674 compares
WORST CASE -- 29.502 secs -- 524799 compares
AVERAGE -- 12.637 secs -- 226186 compares
insertion sort -- random list -- 3.648 secs -- 235252 compares
insertion sort -- semi-random list -- 2.687 secs -- 177063 compares
insertion sort -- ordered list -- 0.039 secs -- 1023 compares
insertion sort -- reverse list -- 8.092 secs -- 523776 compares
insertion sort -- almost sorted list -- 0.582 secs -- 36994 compares
BEST CASE -- 0.039 secs -- 1023 compares
WORST CASE -- 8.092 secs -- 523776 compares
AVERAGE -- 3.010 secs -- 194821 compares
bubble sort -- random list -- 11.288 secs -- 522065 compares
bubble sort -- semi-random list -- 10.342 secs -- 521760 compares
bubble sort -- ordered list -- 0.014 secs -- 1023 compares
bubble sort -- reverse list -- 16.043 secs -- 523776 compares
bubble sort -- almost sorted list -- 7.983 secs -- 516273 compares
BEST CASE -- 0.014 secs -- 1023 compares
WORST CASE -- 16.043 secs -- 523776 compares
AVERAGE -- 9.134 secs -- 416979 compares
Done.
FMR stands for First, Middle, Random (choosing the median of the three).
FML stands for First, Middle, Last, and RRR stands for Random, Random, and
Random, etc.
Gish's Heap sort does a lot better than the one I wrote. His has the
code for swapMem coded inline -- I think I'll try that on the other
algorithms when I get some time. Heap sort is iterative and doesn't
require much extra stack space.
The variations on the Quick sort algorithm are substantially faster,
though they may require some stack space because they are recursive.
These have been coded to use a maximum of log(n) stack space.
Shell sort is the fastest iterative algorithm I tested.
The semi-random data is about 2/3 randomized, and the almost sorted data is
only about 10% randomized. If you'd like to peruse the source code, it's
available for the asking. If you have a good sorting algorithm you think
I might be interested in, send it to: huntley@copper.ucs.indiana.edu
--Haydn Huntley
;; *****************************************************
;; * Haydn Huntley huntley@copper.ucs.indiana.edu *
;; *****************************************************