Hacker Neue

Preferences
klibertp parent
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.
TeMPOraL
> 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.

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

zahlman
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)?
Dwedit
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...
enedil
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).
flexagoon
> Because the recursive implementation is surprisingly straightforward and concise

It's also technically not quicksort

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

How does FP handle the random selection?

klibertp OP
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.)
shpongled
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

shawn_w
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)

tmtvl
Just do the Sedgewick thing and take the median of the first, middle, and last elements.
Arch-TK
Quicksort in FP?

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

riffraff
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

notpushkin
It really shines if you want a shortcut on a whiteboard interview, though.
hinkley
Step six: draw the rest of the fucking owl.

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

This item has no comments currently.

Keyboard Shortcuts

Story Lists

j
Next story
k
Previous story
Shift+j
Last story
Shift+k
First story
o Enter
Go to story URL
c
Go to comments
u
Go to author

Navigation

Shift+t
Go to top stories
Shift+n
Go to new stories
Shift+b
Go to best stories
Shift+a
Go to Ask HN
Shift+s
Go to Show HN

Miscellaneous

?
Show this modal