|
PureBytes Links
Trading Reference Links
|
>Mike said:
>> If you data is in random or near random order, use a quick sort.
>> If the data is in near sorted order already, use a shell sort.
>> Both algorithms are well known and easily available on the net.
Gerart said:
>My data is random and I need a quick sort. I found the algorithm on
>the internet BUT I'm not good enough to translate it into a multi-
>dimensional array quick sort code for Easylanguage, are you?
I can, although I haven't needed to.
Probably the best all-around fast sort to implement in EasyLanguage
is the heapsort, not the algorithm known as "quicksort."
The quicksort requires auxiliary storage. Depending on the
implementation, this auxiliary storage is either allocated
explicitly by the sort routine, or (if the quicksort is implemented
recursively) by the operating system allocating space on its stack.
Quicksort can also become a SLOWsort if the input data happens to be
reverse-ordered. The heapsort, in contrast, is a true "in-place"
sort and nearly as fast (almost indistinguishable in speed from the
quicksort). It also doesn't suffer from becoming a slowsort. Both
quicksort and heapsort require on the order of N log N operations.
C-language source for heapsort is available at
http://www.library.cornell.edu/nr/bookcpdf/c8-3.pdf
The code given is written to sort a 1-dimensional array, but is
easily adaptable to sorting on more dimensions. You just have to
replace the comparison statements and the assignment statements that
involve array elements, with loops or more function calls.
Here's the C and EL code below, for sorting a 1-dimensional array.
See the footnotes for modifying to more dimensions. The C version
assumes that the lowest array index is 1, not 0. I have modified
this in the EL version to use the array indices 0 to N, rather than
1 to N. My translation is on the right (untested).
// Note the footnotes *, **, ***
void hpsort(unsigned long n, float ra[]) // {Function hpsort}
// input: ra[N](NumericArrayRef)
{
unsigned long i,ir,j,L; // vars: i(0),ir(0),j(0),L(0);
float rra; // vars: rra(0),lp1(true),lp2(true);
if (N < 2) return; // if N > 1 then begin
L = (N>>1)+1; // L = IntPortion(0.5*N)+1
ir = N; // ir = N;
for (;;) { // while lp1 begin
if (L > 1) // if L > 1 then begin
rra = ra[--L]; // L=L-1; rra = ra[L]; {*}
else { // end else begin
rra = ra[ir]; // rra = ra[ir]; {*}
ra[ir] = ra[1]; // ra[ir] = ra[0]; {**}
if (--ir == 1) { // ir = ir-1; if ir = 0 then begin
ra[1] = rra; // ra[0] = rra;
break; // lp1 = false; {break from loop}
} // end;
} // end;
i = L; // i = L;
j = L+L; // j = L+L;
// lp2 = true;
while (j <= ir) { // while lp1 and j<=ir and lp2 begin
if (j<ir && ra[j]<ra[j+1]) // if j<ir and ra[j]<ra[j+1] {***}
j++; // then j = j+1;
if (rra < ra[j]) { // if rra<ra[j] {*} then begin
ra[i] = ra[j]; // ra(i)=ra[j]; {**}
i = j; // i=j;
j <<= 1; // j = j*2;
} else // end else
break; // lp2 = false; {break from loop}
} // end; {end of inner while loop}
ra[i] = rra; // ra[i]=rra; {*}
} // end; {end of outer while loop}
} // end; hpsort = 1;
Footnotes:
* rra is temporary holding space for an array element. If you have
a 3-dimensional array with dimensions [X,Y,Z] and you're sorting
it on dimension Y, then rra must be declared as an array having
dimensions [X,Z] and you must substitute the assignment with a loop
that assigns all the array elements in ra[X,i,Z] to rra[X,Z].
** An assigntment like ra[i]=ra[j], for a 3-D array having
dimensions [X,Y,Z] sorted on dimension Y, must be substituted by a
loop assigning all elements for the 'j' index to the 'i' index.
*** For a comparison involving elements in a 3-D array, you will
need to first construct a loop that compares the array elements
for index i on dimension Y the way you want it compared, and end
up with a true or false result. The code shown results in a sort
in ascending order, but the condition ra[j]<ra[j+1] can easily be
replaced by any other condition, or even a function that returns
True or False.
--
,|___ Alex Matulich -- alex@xxxxxxxxxxxxxx
// +__> Director of Research and Development
// \
// __) Unicorn Research Corporation -- http://unicorn.us.com
|