wiki:Quicksort

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]
Last modified 5 years ago Last modified on Nov 17, 2014, 6:31:29 PM
Note: See TracWiki for help on using the wiki.