home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / E / TFF-A32R.LZX / AmigaE3.2a / Src / Lang / Yax / QuickSort.yax < prev    next >
Encoding:
Text File  |  1996-06-06  |  1.9 KB  |  83 lines
  1. /* quick sort in yax, by Ben Schaeffer Nov 1993 */
  2. (write 'Enter array size: ''')
  3. (set size (readint))
  4. (array original size)
  5. (array test size)
  6. (set pivot 0)
  7.  
  8. /* guess at stack size*/
  9. (array stack (/ (+ 1 size) 2))
  10. (set sp 0)
  11.  
  12. /* set up original values */
  13. (for i 0 (- size 1) 
  14.    (set (original i) (rnd 1000))
  15. )
  16.  
  17. /* set up test values */
  18. (for i 0 (- size 1) 
  19.    (set (test i) (original i))
  20. )
  21.  
  22. /* quick sort functions defined here */
  23.  
  24. /* this function must only change pivot */
  25. (defun partition (low high)
  26.    (when (? pivot low)
  27.       (set temp (test low))
  28.       (set (test low) (test pivot))
  29.       (set (test pivot) temp)
  30.    )
  31.    (set pivot low)
  32.    (inc low)
  33.    /* now organize data such that all values greater than pivot will be */
  34.    /* gathered on the higher end of the array and all values less than  */
  35.    /* pivot will be on the lower end of the array */
  36.    (while (not (> low high))
  37.       (if (not (> (test low) (test pivot)))
  38.          (inc low)
  39.          (if (> (test high) (test pivot))
  40.             (dec high)
  41.             (do
  42.                (set temp (test low))
  43.                (set (test low) (test high))
  44.                (set (test high) temp)
  45.             )
  46.          )
  47.       )
  48.    )
  49.    /* this repositions pivot so that it is truly in its ordered location */
  50.    (when (? high pivot)
  51.       (set temp (test high))
  52.       (set (test high) (test pivot))
  53.       (set (test pivot) temp)
  54.    )
  55.    (set pivot high)
  56. )
  57.  
  58.  
  59. (defun quicksort (lo hi)
  60.    (when (< lo hi)
  61.       (set pivot (/ (+ lo hi) 2))
  62.       (partition lo hi)
  63.       (when (< lo pivot)
  64.          (quicksort lo (- pivot 1))
  65.       )
  66.       (when (> hi pivot)
  67.          (quicksort (+ pivot 1) hi)
  68.       )
  69.    )
  70. )
  71.  
  72. (write 'beginning quick sort')
  73. (quicksort 0 (- size 1))
  74. (write 'ended quick sort')(readint)
  75.  
  76. (write 'checking order')
  77. /* show sorted array */
  78. (for i 1 (- size 1) 
  79.    (when (< (test 1) (test 0))
  80.       (write (test i)' _ ' i)
  81.    )
  82. )
  83. (write 'done')