QuickSort(), native code, Force compiler
Author Message
QuickSort(), native code, Force compiler

Hi all,

Quote:
> 1. Created a quicksort in Clipper code for single dimentional arrays.
> ...
> Folks, if you are sorting arrays, you just gotta try this function.
> ...
> This is interesting, I did some testing of the QuickSort() function
> and in my (simple and trivial) test cases it didn't appear to offer
> anything over Clipper's asort().
> ...
> Thanks for looking into this.  For some time, I've been annoyed by
> how slowly Clipper sorts arrays.  I haven't found a replacement
> function yet (and don't know a low level language that would let me
> write one myself).

Here is some code to compare with the previously posted one. It appears
that the simple algorithm used in the sample function, called here
ClipperSort(), is faster than QuickSort() or asort(). In addition,
let me present the same algorithm implemented in the Force language.

//----- Clipper module: test.prg ------------------------------------

proc main
local aArray := {    5,  33,  999,    55,     1, ;
100,  66,    0,     7,    44, ;
1320,  99,  -87, 32767, 32766, ;
-308, 363, 3536,   374, 12209 }
local n
local nTime
? "Started 10,000 iterations of sorting a 20-element integer array"
nTime := seconds()
for n := 1 to 10000                           // measured times (sec)  ?
// QuickSort( aArray )                        // 32.90                 ?
// asort( aArray )                            // 12.58                 ?
// ClipperSort( aArray, len( aArray ) )       //  7.31                 ?
ForceSort( aArray, len( aArray ) )         //  1.82                 ?
next
? "Time elapsed", seconds() - nTime
wait
for n := 1 to 20
? aArray[ n ]
next
return

proc ClipperSort( aArr, nArraySize )
local n
local x, y
local lPass := .f.
do while .not. lPass
lPass := .t.
for n := 1 to nArraySize - 1
x := aArr[ n ]
y := aArr[ n + 1 ]
if x > y
aArr[ n ] := y
aArr[ n + 1 ] := x
lPass := .f.
endif
next
enddo
return

//----- Force module: fsort.prg -------------------------------------

func int _parinfo extern             // Native code compilers, like C
param value int iParamNum            // or Force, require that functions
// are declared before they are
func int _parinfa extern             // used.
param value int  iParamNum, ;        // Such declarations are called
value uint uArrayIndex         // prototypes.
// The prototypes for the standard
func int _parni extern               // functions of these languages are
param value int iParamNum, ;         // placed in include files, similarly
value int iArrayIndex          // to the declarations in Clipper's
// .ch files.
func logical _storni extern          // <=== The four functions declared
param value int iNumber, ;           // here are resident in clipper.lib
value int iParamNum, ;         // and are necessary for accessing
value int iArrayIndex          // Clipper variables from native code.

#define TYPE_NUMERIC   2
#define TYPE_ARRAY   512

#pragma W_FUNC_PROC-

/*
The function below is the exact mirror of the ClipperSort() function
shown above. The only substantial difference is that the elements of
the array passed from the calling Clipper code are accessed via
calls to the above-declared _parni() and _storni() functions, instead
of directly by [index] positions. This sample function deals with integer
arrays only. A more generic array sorter would call the appropriate
data retriever functions in clipper.lib, after checking the type of
the array.
*/

//-------------------
proc ForceSort Pascal
vardef                               // Native code compilers need to know
int     nArraySize                // the data type of all variables.
int     n                         // Such explicit declarations also
int     x, y                      // help the programmer to find bugs
logical lPass                     // during compilation rather than
enddef                               // at runtime.
nArraySize := _parni( 2, 0 )
if    _parinfo( 0 )    != 2 .or. ;            // Here all parameters are
_parinfo( 1 )    != TYPE_ARRAY .or. ;   // type-checked to avoid
_parinfa( 1, 1 ) != TYPE_NUMERIC .or. ; // runtime errors.
nArraySize < 2
return                                     // Return if params invalid.
endif
lPass := .f.
do while .not. lPass                          // The Force language is
lPass := .t.                               // syntactically the closest
for n := 1 to nArraySize - 1               // relative of Clipper
x := _parni( 1, n )                     // amongst all native code
y := _parni( 1, n + 1 )                 // languages. Force has
if x > y                                // speed and power similar
_storni( y, 1, n )                   // to C, but it does not
_storni( x, 1, n + 1 )               // pose the learning curve
lPass := .f.                         // of C, often intimidating
endif                                   // to xBase programmers.
next                                       // In addition, Force has
enddo                                         // the same database commands
endproc                                       // and other xBase elements
// like Clipper.

The above code is written in Force 4.0. This version of Force is
not yet available on the market, so I include the linkable object code
of fsort.prg below in uuencoded form, for your testing convenience.

begin 600 FSORT.OBJ
<encoded_portion_removed>
end

Zoltan (Force Development Team)

____________________________________________________

System Analyst,  DecaGen Software,  Szeged,  Hungary
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Thu, 11 Nov 1999 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages