home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 3 / PDCD_3.iso / pocketbk / developmen / oplexamp / COMBSORT.OPL < prev    next >
Text File  |  1992-09-29  |  2KB  |  70 lines
  1. REM ==========================
  2. REM psion/series3 #2485, from dpalmer, 1349 chars, Sep 14 13:20 92
  3. REM This is a comment to message 2474.
  4. REM --------------------------
  5. REM Until these new-fangled DYLs come to the rescue, consider
  6. REM something along these lines:
  7. REM ---
  8.  
  9. REM OPL combsort demo
  10. global item%(500)
  11. local i%, j%, swaps%, top%, gap%, hold%, size%
  12. size%=500
  13.  
  14. REM Set up sample data
  15. randomize second
  16. i%=1
  17. while i%<=size%
  18.   item%(i%)=int(rnd*32768)
  19.   i%=i%+1
  20. endwh
  21.  
  22. print "Sorting"
  23.  
  24. gap%=size%
  25. do
  26.   gap%=int(gap%*0.769231)
  27.  
  28.   if gap%=0
  29.     gap%=1
  30.   elseif (gap%=9) or (gap%=10)
  31.     gap%=11
  32.   endif
  33.  
  34.   swaps%=0
  35.   top%=size%-gap%
  36.   i%=1
  37.   while i%<=top%
  38.     j%=i%+gap%
  39.     if item%(i%)>item%(j%)
  40.       hold%=item%(i%)
  41.       item%(i%)=item%(j%)
  42.       item%(j%)=hold%
  43.       swaps%=-1
  44.     endif
  45.     i%=i%+1
  46.   endwh
  47. until (gap%=1) and not swaps%
  48.  
  49. print "Sorted"
  50.  
  51. REM ---
  52. REM 
  53. REM In practice you would sort an array containing the record number,
  54. REM having extracted another one with the sort key for each record.
  55. REM 
  56. REM The advantages of CombSort are: its easy to code, it does not
  57. REM require much memory, its not recursive (so its stack usage is
  58. REM bounded), and its O(n*log(n)).
  59. REM 
  60. REM For 500 items Combsort is about 50% slower than QuickSort,
  61. REM however, because it makes significantly more comparisons. So
  62. REM these should be made as fast as possible (hence the sort key
  63. REM array). In practice I have found it to be the only feasible sort
  64. REM in OPL on the Organiser. On the S3, the above routine takes 15
  65. REM seconds, compared to about 11 seconds for QuickSort.
  66. REM
  67. REM David.
  68.  
  69.  
  70.