Arc Forumnew | comments | leaders | submitlogin
3 points by zck 4460 days ago | link | parent

I believe this is a "real" qsort. It's way more verbose than I expected, but I did code it on two nights hours after I should have gone to bed. I'm sure I could name some things better. Maybe I will later.

  (def qsort (lst)
       (let helper (afn (start end)
                        (if (>= start end)
                            lst
                          (let pivot-pos (partition lst start end)
                               (self start
                                     (- pivot-pos 1))
                               (self (+ pivot-pos 1)
                                     end))))
            (helper 0 (- (len lst) 1)))
       lst)


  (def partition (lst (o start 0) (o end (- (len lst) 1)))
       "Partitions a list in-place. 
        This method returns the position the pivot moved to."
       (withs (pivot lst.start
               higher-num-out-of-place (+ start 1)
               lower-num-out-of-place end)
              (until (is higher-num-out-of-place
                         lower-num-out-of-place)
                     (until (or (> lst.higher-num-out-of-place
                                   pivot)
                                (is higher-num-out-of-place
                                    lower-num-out-of-place))
                            (++ higher-num-out-of-place))
                     (until (or (< lst.lower-num-out-of-place
                                   pivot)
                                (is higher-num-out-of-place
                                    lower-num-out-of-place))
                            (-- lower-num-out-of-place))
                     (unless (is higher-num-out-of-place
                                 lower-num-out-of-place)
                       (swap lst.higher-num-out-of-place
                             lst.lower-num-out-of-place)))
              (let pivot-end (if (> lst.higher-num-out-of-place
                                    pivot)
                                 (- higher-num-out-of-place
                                    1)
                               higher-num-out-of-place)
                   (swap lst.start
                         lst.pivot-end)
                   pivot-end)))
examples:

  arc> (qsort (n-of 10 (- (rand 21) 10))) ;; from -10 to 10 inclusive
  (-10 -9 -5 -4 -2 5 6 6 8 9)
  arc> (qsort (n-of 10 (- (rand 21) 10)))
  (-10 -10 -8 -1 3 5 6 7 8 9)