Would You Like a Faster Sort?
Probably more research has been devoted to sort routines than any other algorithm. Literally trillions of items are sorted every day in the computer world, and speed is crucial. If you could produce a sort package that was 5% faster than the best existing algorithms, you probably could name your price.
Well, I haven't written one of those, but I would offer an alternative to your
built-in sorting mechanism. This idea isn't actually a sort at all,
but a linear algorithm — that is, no nested loops. Under certain
conditions, the simple routine shown below can run exponentially faster than
PowerBASIC's ARRAY SORT function.
There are two restrictions. The data must consist of integers; and the
utility array X() must be dimensioned at least to the
size of the greatest data value. So if the value 9,000,000 occurs somewhere
in the data, then
X() must be dimensioned at least to nine million
cells. That is not an issue for PowerBASIC, which supports arrays exceeding
four billion cells.
DIM A(100000000) AS LONG 'integer data to be sorted DIM X(100000000) AS LONG 'dimensioned >= greatest data value DIM SortSize& 'number of data items DIM MaxInt& 'greatest integer in data DIM J&, K&, N& '--------[ Array Map Sort ]-------- FOR J=1 TO SortSize: INCR X(A(J)): NEXT N=1 FOR K=1 TO SortSize 'for DESCENDING order, use: FOR K=SortSize TO 1 STEP-1 DO IF X(N) THEN A(K)=N: DECR X(N): EXIT INCR N LOOP NEXT K
Each value in A() is flagged at the corresponding address of
X(). So if A(any)=375, then X(375)
is incremented. Then variable N steps through X();
whenever a positive value is encountered, the location of N is written
back sequentially to A(). A nifty feature is that
A() doesn't have to be cleared out before being rewritten.
Data which include negative integers can be accommodated either by adding a suitable
offset when writing to
X(), then subtracting that value as it is written
back to A(), or by setting up the array to include negative addresses
in the first place. PowerBASIC lets you do that. Also, using an appropriate
multiplier as an offset would enable the sorting of non-integer values that
conform to a rigid format — such as decimal currency or batting averages.
Because ARRAY SORT was written in assembler, it is of course more inherently
efficient than anything written in a high-level language such as PowerBASIC. That
is the only reason that it can compete with
Array Map at all.
As it is, ARRAY SORT performs better with smaller data
samples — up to about 25,000 items. But for a sort of, say, 50 million
items, Array Map runs 30 times faster on my computer when the
integer size is limited to 100 thousand, and five times faster when the integer values
can range up to 100 million.
This works just like Array Map, except that instead of flagging whole array
elements, each data integer in
A() is represented by a single bit
in X(). The tradeoff is that there can be no matching data values,
unless it is okay that only one of equal values would survive the process.
The sole advantage is that array
X() can be eight times smaller
than before. Admittedly, in today's world of virtually unlimited memory resources,
this routine has become functionally obsolete; I include it just for nostalgia purposes;
for in my DOS/GW-BASIC days it was a godsend.
DIM (as above) DIM EL& 'array element DIM BT& 'bit counter '--------[ BitMap Sort ]-------- FOR J=1 TO SortSize EL=A(J)\32: BT=A(J) MOD 32 BIT SET X(EL),BT NEXT J K=1 FOR EL=0 TO (MaxInt+31)\32 'step through the array FOR BT=0 TO 31 'step through the bits IF BIT(X(EL),BT) THEN N=32*EL+BT: A(K)=N: INCR K IF K>SortSize THEN EXIT,EXIT 'done END IF NEXT BT NEXT EL