3 ms·
> since for some reason in FP languages quicksort is typically next after "hello world" How does FP handle the random selection?
by jason_s 1y ago
> since for some reason in FP languages quicksort is typically next after "hello world"
How does FP handle the random selection?
- klibertp 1y agoThey use the first element. Like, it's random enough, right? :) (I mean, it still works, but goes badly for lists already sorted in reverse, etc.)
- shpongled 1y agoThere's no problem with randomness in FP? You could use a monad/external state for an OS-level RNG, or define a purely functional PRNG
- shawn_w 1y agoIt's usually quicksorting a linked list, where a random pivot, median of three, etc. are terrible for performance. (Merge sort is of course the natural sort for lists, but qs is like 2 lines of Haskell so it gets demoed for being clever)
- tmtvl 1y agoJust do the Sedgewick thing and take the median of the first, middle, and last elements.