quick sort: pivot selection

The most famous quick sort in the functional world is from Haskell. To simplify the problem, all elements in given list are unique.

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort [y | y <- xs, y < x] ++ [x] ++ quickSort [y | y <- xs, y > x]

It works like quick sort until you start attack it.

1. Problem pattern

The following code shows the problem, quick sort performs well if its pivot selection cut list fairly into two parts, at here we always get an empty one, pivot, and rest because we always select head and head is the biggest element in the list.

quickSort [5, 4, 3, 2, 1]

2. Random selection

Thus, the idea is select pivot randomly, by assuming median number is randomly in the given list(we don't know the structure of list).

(require racket/random)

(define/match (qsort l)
  [('()) '()]
  [(lst)
   (define pivot (random-ref lst))
   (append (qsort (filter (λ (x) (< x pivot)) lst))
	   (list pivot)
	   (qsort (filter (λ (x) (> x pivot)) lst)))])

This is a huge improvement for certain pattern, for example

(define target (stream->list (in-range 10000 0 -1)))

(time
 (void (origin-qsort target))))
(time
 (void (qsort target)))

We can see performance compare result here.

length	origin-qsort	random qsort
10000	1218ms	19ms
100000	timeout	239ms
1000000	timeout	2743ms

We still might fall into the worst case, but it is much less than the origin-qsort.

3. Conclusion

Generally, this algorithm is good enough, unless we know some distribution patterns about the given list. Except the pivot selection, we still can do some tricks to improve the performance, but that's not going to be the part at here.