home *** CD-ROM | disk | FTP | other *** search
/ AMOS PD CD / amospdcd.iso / 501-525 / apd520 / asstd_programs / quicksort.amos / quicksort.amosSourceCode
AMOS Source Code  |  1991-01-19  |  2KB  |  88 lines
  1. '--------------------------------- 
  2. ' Quicksort. 
  3. '
  4. ' Robert Farnsworth. 
  5. ' 1 Vidivoc Ave
  6. ' Mildura, 3500
  7. ' Jan. 91. 
  8. '--------------------------------- 
  9. ' If you need to sort more than
  10. ' a single dimension array, try
  11. ' this.
  12. '
  13. ' Times: 
  14. '       Quicksort  Bubble sort 
  15. '   10    0.4         0.4          
  16. '  100    0.8         4.6  
  17. '  500    5.4       117.1
  18. ' 1000   11.7       452.0
  19. ' 2000   26.4          ? 
  20. ' 4000   56.5          ? 
  21. ' 8000  124.8          ? 
  22. '  
  23. ' The times are now lower than above,  
  24. ' now using Swap.
  25. '--------------------------------
  26. '!!!!!!!!!!!!!!!!!!! NOTE TO MANDARIN !!!!!!!!!!!!!!!!!!!!!!!
  27. '
  28. ' Had a lot of trouble writing this, computer kept crashing. 
  29. ' Two problems:
  30. '
  31. ' 1)  With A=2000 I was greeted by the AMOS `message of doom'
  32. '     requester while the quicksort routine was executing. 
  33. '     Had to use Set Buffer. 
  34. ' 2)  The Input statement (rem'd out) also crashed my poor 
  35. '     old 1000 when I entered 1000 - not every time, but often.  
  36. '     Everthing just froze. Had to eliminate Input statement.
  37. '
  38. '     Wonder if this happens on a 500?     
  39. '!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  40. Set Buffer 100
  41. '
  42. 'Input "Array Size ";A 
  43. '
  44. A=1000
  45. Dim ARRAY(A)
  46. Global ARRAY()
  47. Print A;" numbers"
  48. For I=1 To A
  49.    ARRAY(I)=Rnd(2000000)
  50. Next 
  51. '
  52. Print "Sorting..."
  53. Timer=0
  54. 'BUBBLE[1,A] 
  55. QUICKSORT[1,A]
  56. E=Timer
  57. Print(E-S)/50.0
  58. Boom 
  59. End 
  60. '
  61. Procedure QUICKSORT[LO,HI]
  62.    If LO<HI
  63.       K=ARRAY(LO) : L=LO : H=HI
  64.       While L<>H
  65.          While H>L and K<=ARRAY(H)
  66.             Dec H
  67.          Wend 
  68.          Swap ARRAY(L),ARRAY(H)
  69.          While L<H and K=>ARRAY(L)
  70.             Inc L
  71.          Wend 
  72.          Swap ARRAY(L),ARRAY(H)
  73.       Wend 
  74.       QUICKSORT[LO,L-1]
  75.       QUICKSORT[H+1,HI]
  76.    End If 
  77. End Proc
  78. '
  79. Procedure BUBBLE[LO,HI]
  80.    Shared ARRAY()
  81.    For J=HI-1 To LO Step -1
  82.       For I=LO To J
  83.          If ARRAY(I)>ARRAY(I+1)
  84.             T=ARRAY(I) : ARRAY(I)=ARRAY(I+1) : ARRAY(I+1)=T
  85.          End If 
  86.       Next 
  87.    Next 
  88. End Proc