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)
  [('()) '()]
   (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)))

 (void (origin-qsort target))))
 (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.

Date: 2022-01-20 Thu 00:00

Author: Lîm Tsú-thuàn