3 ms·
> for some reason in FP languages quicksort is typically next after "hello world" Because the recursive implementation is surprisingly straightforward and conc
by 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