|
PureBytes Links
Trading Reference Links
|
I said:
>> Probably the best all-around fast sort to implement in EasyLanguage
>> is the heapsort, not the algorithm known as "quicksort."...
Gerart replied:
>I received the following message from someone who didn't reply to
>the omega-list but did reply to me. What is your opinion, Alex? :
>
>"I researched this a while ago...... and there is a big problem with EL
>because it does not support recursion...... thus, QUICKSORT is out.
He's right about that, although one can implement the quicksort
using an auxiliary array, and not require recursion. Numerical
Recipes has an example of that.
>I painstakingly implemented a HEAPSORT in EL, that does NOT change
>the order of the data in the array, but returns an array of new array offsets
>that are pointers to the array in sorted order. Better than a bubble sort,
>however, I was still not impressed with the performance. Best to go with
>a "C" based DLL"
What I posted earlier does change the order of the data in the
original array. I patterned it after the bubble sort example in the
EL documentation.
Mine, however, won't be as efficient as what this other fellow
described above. What he did was modify the heapsort to act
as an index sort. So instead of swapping a large number of
data items around, he just builds a 1-dimensional array of
indexes that represent the original array element positions
reshuffled into sorted order. This is more efficient if the array
elements you are sorting are each large (like each element is
itself a multidimensional array or some other data structure).
It's also more work for whoever uses this sort routine. For
single-dimensional arrays, mine is more efficient and easier.
He's probably right that EL isn't the place to do it. EL will
never be as fast as a compiled C program. The heapsort is the most
efficient algorithm known next to the quicksort, but possibly EL
has so much other overhead that the savings you get don't amount to
much.
--
,|___ Alex Matulich -- alex@xxxxxxxxxxxxxx
// +__> Director of Research and Development
// \
// __) Unicorn Research Corporation -- http://unicorn.us.com
|