Wednesday, November 24, 2010

Since every programming blog must have a quicksort implementation...

The following demonstrates a simple quicksort implementation written in Groovy.

def qsort(list){
    if ((size = list.size()) < 2) return list
    def groups = list.groupBy{it <=> list[size>>1]}.withDefault{[]}
    qsort(groups[-1]) + groups[0] + qsort(groups[1])
}

While not particularly optimized (Though not terrible), it is quite concise.  The use of 'groupBy' allows one to whittle down the typical iterate-and-check strategy rather nicely, though I had to add an empty list as a default to avoid passing null (which occurs if the pivot is an edge-case).

This version will sort anything that implements the Comparable interface (like the built-in sort method), as evidenced by the use of the colloquial "UFO" (<=>) operator.

This is all, of course, simply an academic exercise - More to demonstrate groupBy and withDefault than anything else ( two methods that I'm finding eminently useful in an increasingly wide variety of situations).

Cheers.

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home