Tee hee. I couldn't resist knocking up a quick C program to compare quick/heap sorts.
I forced them to have identical calls, which were to sort pointers to data. The call took an array of pointers to <whatever>s, a count of how many <whatever>s there were and a pointer to a routine that would return the result of comparing the <whatever> pointed to by one pointer with the <whatever> at another pointer. With <whatever>s that happened to be double floating point values, and repeating each test for about two seconds, I got the following results for "heapsort": 1000 433.84us(0.0628047) 529.661us(0.0766763) 717.87us(0.103923) 2000 951.47us(0.0625896) 1154.73us(0.0759603) 1477.10us(0.097166) 3000 1488.10us(0.0619547) 1801.80us(0.0750154) 2570.69us(0.107027) 4000 2036.66us(0.0613892) 2421.31us(0.0729833) 3367.00us(0.101489) 5000 2624.67us(0.0616323) 3086.42us(0.0724750) 4329.00us(0.101653) 6000 3289.47us(0.0630203) 3773.58us(0.0722949) 5291.01us(0.101366) 7000 3906.25us(0.0630288) 4424.78us(0.0713954) 6410.26us(0.103432) 8000 4504.50us(0.0626517) 5128.21us(0.0713265) 6993.01us(0.097263) 9000 5291.01us(0.0645679) 5847.95us(0.0713645) 8196.72us(0.100027) The columns are the item count, sorting where all inputs are identical, sorting where the input is already sorted and sorting where it is random (but all unique values). The number in brackets is the time divided by n*ln(n). You can see the sort working a bit harder in each case, and being pretty consistent down the columns. It actually seems to improve quite a bit with pre-sorted data. The amusing part is what happened with quicksort: 1000 12658us( 1.83247) 229.73us(0.0332563) 705.22us(0.1020910) 2000 50500us( 3.32197) 528.82us(0.0347867) 1466.28us(0.0964541) 3000 112222us( 4.67221) 839.63us(0.0349568) 2173.91us(0.0905077) 4000 200000us( 6.02842) 1114.83us(0.0336032) 2785.52us(0.0839613) 5000 310000us( 7.27939) 1485.88us(0.0348914) 3831.42us(0.0899690) 6000 453333us( 8.68503) 1801.80us(0.0345192) 4739.34us(0.0907970) 7000 610000us( 9.84257) 2145.92us(0.0346253) 5434.78us(0.0876922) 8000 800000us(11.1269 ) 2369.67us(0.0329589) 6493.51us(0.0903161) 9000 1020000us(12.4474 ) 2801.12us(0.0341830) 7246.38us(0.0884300) OK. So the random order - quicksort marginally outperforms heapsort. For the already sorted case, quicksort is rather better than heapsort, but its margin goes down as the count goes up. However, with the data all the same... ooopppsss.... my quicksort has fallen headlong into the O(n*n) trap. _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
