External sort compo?

[Antoni Gual]

Here are a set of rules. Excuse the delay. Any suggestion?
And if everyone agrees, let's go!

Rules for QBN external sort compo May 2006

The goal is to design the fastest program to sort an array of data that does'nt fit in the computer's memory.

No prizes, unless we find a sponsor

Deadline, may 29 2006.

There are two categories:
-QuickBasic 4.5
-FreeBasic

QuickBasic entries must sort an array of 1,000,000 (1E6) LONGs without using EMS or XMS or a RAM drive.

FreeBASIC entries must sort an array of 100,000,000 (1E8) INTEGERS, not being allowed to use more than 100Mb of memory (use it at your risk, my PC could start swapping to memory after that). No memory RAM allowed.

No external libraries are allowed, except QB.LIB for QB and CRT.LIB for FB.

No shelling to external programs is allowed.

The entries must be in BASIC source code (so we can learn from our errors), to be compiled locally with QB4.5 or FB 0.15 for Windows

Details:

The input of the program will be the file "unsortfb.dat" or "unsortqb.dat" containing the array to be sorted, the output will be a different file "sort.dat" containing all the registers sorted in increasing order.

The input file can not be overwritten and the output file must have the same size as the input file.

Auxiliar files and directories up to 2GB can be created and must be erased before the end of the program.

The executable and the input,output and auxiliar files will be in the same disk. Absolute paths in the code will probably not work.

The program must terminate by itself, not requiring the use to press a key (to allow me to use a batch file to run them).

The input files can be generated in place with the following programs:

For QB expect a running time of 10 seconds.

Code:

'qbcrea.bas
DIM T!, i, j, b$
b$ = "|\                                     \| ###% Done "

T! = TIMER
OPEN "unsortqb.dat" FOR RANDOM AS #1 LEN = 1000
PRINT "Creating unsortqb.dat."
DIM a AS STRING * 1000
DEF SEG = VARSEG(a)
s& = VARPTR(a)
FOR i = 1 TO 4000
  
  FOR j& = 0 TO 999
    if (j& and 3&) =3& then
     POKE s& + j&, (RND * 127)
    else
     POKE s& + j&, (RND * 256)
    end if
  NEXT
  PUT #1, i, a
  IF (i MOD 100) = 0 THEN
    LOCATE 2, 1
    PRINT USING b$; STRING$(i \ 100, "."); i \ 40;
   END IF
NEXT
CLOSE
PRINT
PRINT "File created in ";TIMER - T!;" seconds. ";LOF(1);" bytes size"
PRINT "Press a key"
SLEEP

For FreeBasic expext a running time of 1.5 minutes.

Code:

'fbcrea.bas
option explicit
dim t!,i,j ,b$,cnt&,l&
b$="|\                                     \| ###% Done "

t!=timer
open "unsortfb.dat" for random as #1 len=1000
print "Creating unsortfb.dat."
dim a as string*1000
for i=1 to 400000
  for j=0 to 999
    if (j and 3)=3 then
     a[j]=int(rnd*128)
    else
     a[j]=int(rnd*256)
    end if
  next
  put #1,i,a
  if (i mod 10000)=0 then
    locate 2,1
    print using b$;string(I\10000,".");i\4000;
   end if
next
CLOSE
PRINT
PRINT "File created in ";TIMER - T!;" seconds. ";LOF(1);" bytes size"
PRINT "Press a key"
SLEEP

Testing:

-The testing will take place in my (Antoni's) computer, if no one else volunteers.
P4 1,44 with 256Mb RAM, W2000 SP4

-Every entry will be compiled and put in a separate folder with its input data.
-Disk will be defragged, antivirus will be stopped.
-Each entry will be run, timed and the results checked for accuracy.

-If an entry takes all night to run, stops waiting for a key ,forgets to erase auxiiar files or damages my computer it will be disqualified and you will hear me ranting for weeks.

-The testing for the correctness of the output file will be made by comparison of all outputs in the same category using DOS's FC. If one output does not match, it will be suspect...

This program can be used too to test the sorting

Code:

open "sort.dat" for random as #1 len =4
dim l&,l1&,cnt&
get #1,,l&
cnt&=1
do
get #1,,l1&
if l&>l1& then
print "Error: ";l&;" > ";l1&;" at position ";cnt&
exit do
end if
l&=l1&
loop until eof(1)  
close