/* quick sort in yax, by Ben Schaeffer Nov 1993 */
(write 'Enter array size: ''')
(set size (readint))
(array original size)
(array test size)
(set pivot 0)

/* guess at stack size*/
(array stack (/ (+ 1 size) 2))
(set sp 0)

/* set up original values */
(for i 0 (- size 1) 
   (set (original i) (rnd 1000))
)

/* set up test values */
(for i 0 (- size 1) 
   (set (test i) (original i))
)

/* quick sort functions defined here */

/* this function must only change pivot */
(defun partition (low high)
   (when (? pivot low)
      (set temp (test low))
      (set (test low) (test pivot))
      (set (test pivot) temp)
   )
   (set pivot low)
   (inc low)
   /* now organize data such that all values greater than pivot will be */
   /* gathered on the higher end of the array and all values less than  */
   /* pivot will be on the lower end of the array */
   (while (not (> low high))
      (if (not (> (test low) (test pivot)))
         (inc low)
         (if (> (test high) (test pivot))
            (dec high)
            (do
               (set temp (test low))
               (set (test low) (test high))
               (set (test high) temp)
            )
         )
      )
   )
   /* this repositions pivot so that it is truly in its ordered location */
   (when (? high pivot)
      (set temp (test high))
      (set (test high) (test pivot))
      (set (test pivot) temp)
   )
   (set pivot high)
)


(defun quicksort (lo hi)
   (when (< lo hi)
      (set pivot (/ (+ lo hi) 2))
      (partition lo hi)
      (when (< lo pivot)
         (quicksort lo (- pivot 1))
      )
      (when (> hi pivot)
         (quicksort (+ pivot 1) hi)
      )
   )
)

(write 'beginning quick sort')
(quicksort 0 (- size 1))
(write 'ended quick sort')(readint)

(write 'checking order')
/* show sorted array */
(for i 1 (- size 1) 
   (when (< (test 1) (test 0))
      (write (test i)' _ ' i)
   )
)
(write 'done')