7 ms·
> I think quicksort is easy to implement, if you know Hoare's fp insight Could you please provide more information on this?
by maleldil 3y ago
> I think quicksort is easy to implement, if you know Hoare's fp insight
Could you please provide more information on this?
- hyperthesis 3y agoHe learnt about recursion in a fp workshop(?), and as a first exercise, tried applying it to sort. You pick a number in the list, then put lesser numbers into a left-list, and greater into a right-list. Recurse. It's very slow as intuitive, simple and elegant fp, because it's creating new lists like crazy; but a mutable, in-place version (e.g. in C) is super fast. Maybe the origin of the folklore "learn fp to be a better coder, not to code fp"? I don't think he expected it to be so good; he was just doing him. A very smart man.