[<<Previous Entry]
[^^Up^^]
[Next Entry>>]
[Menu]
[About The Guide]
XPqsort()
General Purpose Sorting function
------------------------------------------------------------------------------
Function: XPqsort()
XPqsort() is a general purpose Sorting function.
It can be usd to sort whatever one wants to sort.
It was written as a test for Clipper 5.01 and recursion,
and as it works, I added it to the Library. It can for
instance be used to make a Real-Time database sorter,
where a DBF is sorted at real-time, on a network, without
the need of an extra Temporary file. But it could of course
also be used on Binary files or whatever. It's all up to
your imagination!
Note that this function is not quite faster than Clipper's
aSort(), but it doesn't have the drawback that it only can be
used on Arrays.
Syntax: XPqsort(n1st,nLast,bLess,bSwap) --> NIL
Arguments: n1st and nLast indicate the 1st and Last elements
of the sort, and HAVE to be supplied both. bLess is
a code-Block, that is evaluated with two index
arguments, and it should return .t. when the first
element "is less" than the 2nd Element. bSwap is also
a code-Block, with the same 2 arguments, and it should
"Swap" the two elements when evaluated. Note that bLess
and bSwap were not combined in a single code-Block, as
the Quicksort algorithm use's bLess more often than bSwap.
Note that the procedure depth must be a Least Log base 2
of the #of elements to sort. This means that sorting for
instance 1 Million elements (in a database), requires
a procedure depth of 20 (2^20 is just over 1 Million).
Returns: NIL
Usage: As the function is short, here's the Full source (!):
Function XPqsort(nFirst,nLast,bLess,bSwap)
/***
* nFirst and nLast are the First
* resp Last Element index to Sort
* bLess is called with two indices (!),
* returns .t. when Less, .f. otherwise
* bSwap is called with two indices (!),
* should execute the Swap
* (This function is called recursively)
*/
Local i := nFirst
Local j := nLast
Local x := int( (i+j)/2 )
While i<=j
While Eval(bLess,i,x);i++;End
While Eval(bLess,x,j);j--;End
if i<=j
Eval(bSwap,i++,j--)
end
end
if nFirst<j
XPqsort(nFirst,j,bLess,bSwap)
end
if i<nLast
XPqsort(i,nLast,bLess,bSwap)
end
Return (NIL)
And here's an example:
It's a Single User Sort of a database.
Could be adapted for Multi User, without requiring
Exclusive use, Even the flock() could be in the
Swap routine, where some people might still update the
database (for daily sort, for instance, but still run).
XPqsort(1,LastRec(),{|i,j|Compare(i,j)},{|i,j|Swap(i,j)})
Where:
Function compare(i,j)
// Let's Say Sort criterium is the 2nd Field..
Local x,y
dbGoto(i)
x := FieldGet(2)
dbGoto(j)
y := FieldGet(2)
Return (x<y)
And:
Function Swap(i,j)
//Single user Swap, could add flock() etc....
//Also a message indiciting progress could be displayed..
Local x,y
dbGoto(i)
x := XPaFieldGet()
dbGoto(j)
y := XPaFieldGet()
XPaFieldPut(x)
dbGoto(i)
XPaFieldPut(y)
return (NIL)
That's it!
This page created by ng2html v1.05, the Norton guide to HTML conversion utility.
Written by Dave Pearson