home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / MISC / TNH_PC.ZIP / WESTENDP.NL < prev    next >
Encoding:
Text File  |  1987-01-14  |  3.8 KB  |  134 lines
  1. BASIC Sort Using A RAM Disk
  2.  
  3.             Fred Westendarp
  4.       Phoenix IBM PC Users Group
  5.  
  6. Sorting lists is a common programming
  7. task. This can be a problem when
  8. using BASIC because of the memory
  9. limitation (64K) placed on BASIC's
  10. workspace. For example, a list of
  11. 4000 items, each representing a
  12. string of 20 characters, would
  13. require (2500 x 20) = 80K bytes of
  14. array space! This does not consider
  15. the room required for the program
  16. itself, and sorting tasks of larger
  17. proportions are not uncommon. One
  18. solution is to leave the data on the
  19. disk instead of loading it into an
  20. array in BASIC memory. No array space
  21. would be required, and a list of
  22. items filling an entire disk could be
  23. sorted (360K). This concept brings
  24. larger sorting tasks into the realm
  25. of possibility. However, sorting to a
  26. disk has its drawbacks: the number of
  27. disk reads and writes required is
  28. objectionable and will have your
  29. drive unit smoking (figuratively) in
  30. no time. But worst of all, sorting to
  31. a disk is slow!
  32.  
  33. One solution is to sort to a RAM
  34. disk. The data is in the PC memory,
  35. so no time consuming mechanical disk
  36. access is required. In addition, the
  37. data is outside of BASIC`S 64K
  38. program area, leaving plenty of room
  39. for your program.
  40.  
  41. The basic procedure is to first
  42. create a RAM disk. In the following
  43. example, I create RAM disk C:,
  44. consisting of 160K bytes, prior to
  45. booting BASIC. Step two is to create
  46. a file on disk C: which contains the
  47. data to be sorted. This file could be
  48. called C:ARRAYFILE. Next, load the
  49. file with data from your floppy disk,
  50. sort the data on the RAM disk, then
  51. write it back to the floppy.
  52.  
  53. The following example assures the
  54. existence of the RAM disk C:, and a
  55. file called NAMES.DAT on drive A:.
  56. The NAMES.DAT file consists of 4000
  57. records, each 20 bytes in length,
  58. containing a list of names. The names
  59. are in random order, and the task is
  60. to alphabetize them! This represents
  61. 89K worth of data, and could not be
  62. loaded into an array in BASIC's
  63. memory.
  64.  
  65. 1   ' * * Program:  DEMO.BAS
  66.   Includes demo of RAM-SORT      *
  67. 2   ' * * Requires: RAM Disk C: of
  68.  size adequate to hold array to  *
  69. 3   '               be sorted
  70. 4   ' * * Fred Westendarp / Tempe,
  71.  AZ / January,1984 *
  72. 5   '
  73. 10  OPEN "A:NAMES.DAT" AS #1 LEN=20
  74.       'open for random access.
  75. 20  FIELD #1,20 AS NAM$
  76.       'field the buffer.
  77. 30  OPEN "C:ARRAYFILE" AS #2 LEN=20
  78. 40  FIELD #2,20 AS ARF$
  79. 50   FOR LOOP=1 TO 4000
  80.       'for each data record:
  81. 60     GET #1,LOOP
  82.      'get it off the floppy,
  83. 70     LSET ARF$=NAM$
  84.      'set to buffer,
  85. 80     PUT #2,LOOP
  86.      'and write it to RAM disk.
  87. 90   NEXT LOOP
  88. 100  ITEMS=4000 : GOSUB 500
  89. p2     'RAM-SORT Subroutine
  90. 110  CLOSE #1
  91.      'leave A:NAMES.DAT intact,
  92. 120  OPEN "A:NAMES.SOR" AS #1 LEN=20
  93.      'and write sorted list to new file.
  94. 130  FIELD #1,20 AS NAM$
  95. 140  FOR LOOP=1 TO 4000
  96.      'for each record:
  97. 150  GET #2,LOOP
  98.      'get record from C:ARRAYFILE,
  99. 160  LSET NAM$=ARF$
  100.      'set to buffer
  101. 170  PUT #1,LOOP
  102.      'and write it to floppy disk.
  103. 180  NEXT LOOP
  104. 190  CLOSE
  105.      'close the disk files
  106. 200  END
  107. 499  '= = = = = = = = = = = RAM-SORT
  108.  SUBROUTINE (Shell-Metzner) = = = = =
  109. 500  NN = ITEMS + 1
  110.      'ITEMS=count passed from above.
  111. 510  M = NN
  112.      'other sort routines could
  113. 520  M = INT(M/2)
  114.      'be substituted for this one.
  115. 530  IF M = O THEN 710
  116. 540  KK = NN - M
  117. 550  J =1
  118. 560  I = J
  119. 570  LL = I + M
  120. 580  GET #2,I : AR1$ = ARF$
  121. 590  GET #2,LL : AR2$ = ARF$
  122. 600  IF AR1$ <= AR2$ THEN 680
  123. 610  ART$ = AR1$
  124. 620  AR1$ = AR2$
  125. 630  AR2$ = ART$
  126. 640  LSET ARF$ = AR1$ : PUT #2,I
  127. 650  LSET ARF$ = AR1$ : PUT #2,I
  128. 660  I = I - M
  129. 670  IF I >= 1 THEN 570
  130. 680  J = J + 1
  131. 690  IF J = KK THEN 520
  132. 700  GOTO 560
  133. 710  RETURN
  134.