|
PureBytes Links
Trading Reference Links
|
I wrote:
>> In spite of the comment saying it's a "very fast" sort routine,
>> it's not.
Dennis replied:
> Do you know this from experience or are you merely assuming it based on
> a mental image of how you think it works?
Both. I have done extensive speed testing on all different kinds of
sorts, including this one he calls an "exchange sort" which is really
nothing more than a bubble sort using different loop indexing. The fact
remains that it's an O(N^2) sort, the slowest kind.
Now, I will say that WITHIN the family of O(N^2) sorts, the exchange sort
IS the most efficient. And furthermore, for small arrays it can be more
efficient than a O(N log N) sort. After a certain array size (say 100
elements or so), this family of sorts becomes slowest.
> Bubble Sort...: 66.13 Seconds
> Insertion Sort: 35.53 Seconds
> Heap Sort.....: 27.91 Seconds
> Shell Sort....: 16.70 Seconds
> Quick Sort....: 6.59 Seconds
> Exchange Sort.: 4.61 Seconds
That doesn't match my experience at all.
The bubble, insertion, and exchange sort are all O(N^2) sorts, and should
be at the top of that list. Shell's algorithm is in the middle, as well
as the combsort (not mentioned), these being O(N^1.2). Quicksort and
heapsort, both O(N log N) should be similar in performance for large
randomly-ordered arrays, although quicksort reverts to a "slowsort" if the
input array is reverse-ordered.
The O(N log N) sorts CAN be written inefficiently, however. An
implementation of quicksort, for example, that makes use of OS-dependent
stack handling in lieu of auxiliary storage may slow down significantly on
a processor that has few user registers (as with the Intel line of CPUs,
at least up to the 80386). I remember being surprised by that in the
early 1990s when I observed that a 7 MHz MC68000 Amiga outperformed a 40
MHz 80386 DOS PC using the same sort code on each, and the same compiler
as well.
I think this Bob Brickey fellow made some errors, or created some code
having huge overhead handling problems for the more efficient sorts.
> An exchange sort compares each element, starting with the first, with
> every following element. If any of the following elements is smaller
> than the current element, it is exchanged with the current element and
> the process is repeated for the next element.
The above describes EXACTLY the source code for TradeStation's SortUp_a
function. Look at it. It's a bubble sort. It's slow. It should be OK
for most TradeStation uses that deal with small arrays, though. If I had
to sort an array of 1000 elements, I'd use something else.
-Alex
|