# Quicksort

The *imperative* quicksort algorithm could be expressed like this:

If it is an empty list, then it is already "sorted". We are done.

Otherwise, let's take one element from a given non-empty list. It is easier to take the first one - the "head" of the list - so, let's take it.

Now let's *create two new lists* - one with all the elements which are *lesser* than the first element and another with elements *greater or equal* than the first element.

Let's *sort* each of these new sub-lists and *concatenate* the results. `(append (sort lesser) (sort greater-or-equal))`

Translating this into the code we would get some **crap** like this:

(define (quicksort ns) (if (null? ns) ns (let loop ((x (car ns)) (ys '()) (zs '()) (xs ns)) (cond ((null? xs) (append (sort ys) (sort zs))) ((<= (car xs) x) (loop x (cons (car xs) ys) zs (cdr xs))) ((> (car xs) x) (loop x ys (cons (car xs) zs) (cdr xs)))))))

Which is very straight-forward *imperative* code, with lots of variables and a helper function with 4 parameters.

It is an *iterative processes* expressed as constant-space recursive procedure - an iterative loop is implemented as a *tail-recursive* helper procedure.

**This is very poor style**. Some special macros from Common Lisp like `(dolist ...`

or `(loop ... collecting ...`

would be much better.

The *functional* quicksort algorithm could be expressed like this:

This is a *divide-and-conquer* algorithm. So, we should "divide" (*partition*), "process" (*sort*) each part independently and then "combine" (*concatenate*) the results of the sub-processes.

This must be expressed as a *function composition* - we must describe **what to do** with *expressions* (instead of imperative **how to do** with *assignments* and *statements*).

BTW, which procedure should we use for sorting parts? Why, `quicksort`

, of course!

(define (quicksort xs gt?) (if (null? xs) '() (append (quicksort (filter (lambda (x) (gt? (car xs) x)) (cdr xs)) gt?) (list (car xs)) (quicksort (filter (lambda (x) (not (gt? (car xs) x))) (cdr xs)) gt?))))

First of all, look at this - **there is no loop**. Let's look again: *there is no loop*. Only expressions.

This literally says *"append (combine) three *sorted* sub-lists (partitions) created from the original list by filtering out values which are great than and not greater than its first element"*. Just partitioning is not enough - we need sorting.

The same idea (algorithm) expressed with function composition (what to do) in Standard ML:

fun quicksort [] = [] | quicksort (x::xs) = let val (left, right) = List.partition (fn y => y<x) xs in quicksort left @ [x] @ quicksort right end

and Haskell:

import Data.List qsort [] = [] qsort (x:xs) = qsort ys ++ x : qsort zs where (ys, zs) = partition (< x) xs

We are re-using `partition`

form Data.List

The essence of quicksort algorithm expressed in Haskell

f [] = [] f (x:xs) = f ys ++ [x] ++ f zs where ys = [y | y <- xs, y < x] zs = [z | z <- xs, z >= x]

Here is the same algorithm expressed using list-comprehensions (a syntactic sugar for defining lists).

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

**Note:**See TracWiki for help on using the wiki.