QuickSort in Clojure
This past weekend I had the chance to delve more into Clojure’s core library. I experimented with some interesting aspects of the library by implementing the QuickSort algorithm in a couple of different ways.
Random Number Generation
Using the above function we are able to take advantage of lazy sequences to create an infinite list of random integers.
This infinite list is made finite (using
take) when supplying the function with the desired amount of numbers required.
The first implementation documented declaratively describes the QuickSort algorithm, using collection filtering to split the input based on the selected pivot.
The second implementation removes the duplication created by the two filtering predicates, specifying a single
greater? function which is used by both filtering and subsequently removing (the inverse) from the supplied collection.
We also employ the use of the lazy concatenation function which returns a lazy sequence which is only evaluated when required.
The final implementation uses the
group-by function provided by the core library.
Using this function neatly allows us to partition the collection into two separate lists in an extremely expressive manner.
We are then able to destructure the returned map, assigning the true and false values to more clearly named lesser and greater variables.