Arc Forum | Simple quicksort in arc

Arc Forum

Simple quicksort in arc

4 points by akkartik 4463 days ago | 6 comments

I can't believe this hasn't come up here before, but it's true. Inspired by http://blog.thezerobit.com/2012/09/01/beautiful-quicksort-in-common-lisp.html:

  (def qsort(l)
    (iflet (p . xs) l
      (join (qsort:keep [< _ p] xs) list.p (qsort:keep [>= _ p] xs))))

That compares pretty well with haskell:

  qsort (p:xs) = qsort [x | x<-xs, x<p] ++ [p] ++ qsort [x | x<-xs, x>=p]

I actually find keep with the anonymous arg more readable than the list comprehensions.

Is there some way to get haskell's implicit handling of empty lists?

I spent some time trying to build qsort using anarki's partition. No luck.

2 points by rocketnia 4462 days ago | link

"Is there some way to get haskell's implicit handling of empty lists?"

I'm pretty sure there's no implicit handling of empty lists. I think the blog author just left out the base case.

---

"I actually find keep with the anonymous arg more readable than the list comprehensions."

I tend to find list comprehensions unreadable anyway. Using `filter` instead of list comprehensions yields fewer tokens in Haskell, too:

   qsort [] = []
  -qsort (p:xs) = qsort [x | x<-xs, x<p] ++ [p] ++ qsort [x | x<-xs, x>=p]
  +qsort (p:xs) = qsort (filter (< p) xs) ++ [p] ++ qsort (filter (p <=) xs)

Note Haskell's special shorthands for currying infix operators. The expression (< p) means a function that performs (input < p), while (p <=) means a function that performs (p <= input).

I know, the point wasn't to talk about Haskell....

---

"I spent some time trying to build qsort using anarki's partition . No luck."

Here's what I found. It does have fewer tokens after all. ^_^

   (def qsort(l)
     (iflet (p . xs) l
  -    (join (qsort:keep [< _ p] xs) list.p (qsort:keep [>= _ p] xs))))
  +    (apply + (intersperse list.p (map qsort (partition [< _ p] xs))))))

Note that 'partition returns (true-elements false-elements). It could reasonably go the other way around.

---

As the first blog commenter notes, "I believe that that commonly cited example of quicksort in Haskell is not really quicksort, in that it does not have the space and time complexity of quicksort." This is probably true of these Arc snippets as well. Could we get a "real" Arc quicksort?

Also, none of these implementations is a stable sort.

-----

3 points by zck 4460 days ago | link

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)

-----

3 points by rntz 4461 days ago | link

Both Haskell & Arc quicksort are functional (they don't mutate their input), which means they can't have quicksort's usual O(1) additional space overhead. Their time complexity is the same, though.

In-place quicksort is most easily done with an array-like datastructure, so vectors for Arc (if they're mutable, which I think they are). It's probably possible to do it by mutating conses as well, but it would be tricky.

-----

2 points by akkartik 4461 days ago | link

Thanks for the tip on currying infix!

I chose to ignore the pedantry on what is and isn't a quicksort :) Hoare's original algorithm has been mutated several times, and I think it's subjective which of those mutations deserves the name and which doesn't. Especially in high-level languages that encourage programmers to ignore low level concerns of space usage. Wikipedia calls the copying version a 'simple' quicksort (http://en.wikipedia.org/wiki/Quicksort#Simple_version), so I went with that title. I think it's equally valid to call the in-place quicksort a destructive quicksort, like the difference between reverse and nreverse in Common Lisp.

-----

1 point by akkartik 4460 days ago | link

Why do you say they aren't stable? I need to add a comparer to test stability:

  (def qsort(l <)
    (iflet (p . xs) l
      (+ (qsort (keep [< _ p] xs) <)
         list.p
         (qsort (rem [< _ p] xs) <))))

..but that aside I think the sort will be stable, because later equal elements always end up in the last qsort, and rem is stable.

-----

2 points by rocketnia 4460 days ago | link

That makes sense. I spoke too soon. :)

-----