Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


> 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.


It’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.


Am I alone in that I always felt like mergesort was easier to explain (and the O(n lg n) behaviour was easier to prove)?


Merge 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...


O(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).


> Because the recursive implementation is surprisingly straightforward and concise

It's also technically not quicksort


> since for some reason in FP languages quicksort is typically next after "hello world"

How does FP handle the random selection?


They 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.)


There'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


It'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)


Just do the Sedgewick thing and take the median of the first, middle, and last elements.


Quicksort in FP?

Surely you mean mergesort, that's the classic FP sorting example.


quicksort, 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


It really shines if you want a shortcut on a whiteboard interview, though.


Step six: draw the rest of the fucking owl.

Yeah this is lousy. This wouldn’t teach anyone anything.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: