quick sort: pivot selection
source link: https://dannypsnl.github.io/blog/2022/01/20/cs/quick-sort/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.
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]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.
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK