5 ms·
If I didn't know how quicksort works - and I had to learn, since for some reason in FP languages quicksort is typically next after "hello world" - I would strug
by klibertp 1y ago
If I didn't know how quicksort works - and I had to learn, since for some reason in FP languages quicksort is typically next after "hello world" - I would struggle to make sense of the pictures, I think. However, it's absolutely brilliant as a memory refresher: it packs so much info in so little space that it's insanely efficient. I imagine it would pair well with a good textbook on algorithms.
- 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.
- Arch-TK 1y agoQuicksort in FP? Surely you mean mergesort, that's the classic FP sorting example.
- riffraff 1y agoquicksort, e.g. the haskell[0] example is quite well known. Problem is, it's not real since it doesn't work in place defeating the whole point. [0] https://qnikst.github.io/posts/2020-10-18-quicksort.html https://qnikst.github.io/posts/2020-10-18-quicksort.html
- notpushkin 1y agoIt really shines if you want a shortcut on a whiteboard interview, though.
- TeMPOraL 1y ago> for some reason in FP languages quicksort is typically next after "hello world" Because the recursive implementation is surprisingly straightforward and concise, and more-less demonstrates what the whole paradigm is about. As much as I hate to admit it, it's a good learning artifact.
- zahlman 1y agoAm I alone in that I always felt like mergesort was easier to explain (and the O(n lg n) behaviour was easier to prove)?
- Dwedit 1y agoMerge Sort is much easier to explain when you do the non-recursive version that's upside-down. Merge size 1 together, merge size 2 together, merge size 4 together, merge size 8 together, etc...
- enedil 1y agoO(n lg n) is indeed hard to prove for quicksort, because it is not even true in the general case. Worst case is O(n^2).
- hinkley 1y agoIt’s straightforward to a programmer. Who doesn’t need an ikea diagram in the first place. This is why developer docs are trash. Because 90% of us can’t even identify when we are talking over everyone’s heads.
- flexagoon 1y ago> Because the recursive implementation is surprisingly straightforward and concise It's also technically not quicksort
- hinkley 1y agoStep six: draw the rest of the fucking owl. Yeah this is lousy. This wouldn’t teach anyone anything.