Laurence Reeves writes; > Tee hee. I couldn't resist knocking up a quick C program to compare > quick/heap sorts. <> > 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.
On the other hand, in cases 'pre-sorted' and 'data all the same', a plain binary insertion sort appears to outperform them both /considerably/ (just tested). (However, with only a tiny degree of irregular data in an otherwise pre-sorted or same data set, performance deteriorates rapidly.) Conclusion: Quicksort is a great all-rounder. In cases where you have some prior knowledge of the input data you could supplement that with a heapsort or, if the sets are small and the data is relatively pure, a binary insertion sort. I have also found that where tiny amounts of data (<= 10 elements) need to be sorted, a bubblesort is so simple to implement in just a few lines of Basic, that its not worth bothering with anything else. Per _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
