5 ms·

On the slides for quick-sort, the author asks: > Why don’t they teach it like that in the algorithms course?) I'm sure they do sometimes. However, it is incor

On the slides for quick-sort, the author asks: > Why don’t they teach it like that in the algorithms course?) I'm sure they do sometimes. However, it is incorrect because quick-sort is an O(nlogn) in-place sort. This is a best-case O(n^2) sort (due to the linked-list appending) and is not in-place. If you got taught this as quick-sort ask for a refund... ;) --- Honestly, there's isn't anything very interesting in these slides assuming you already know basic functional programming. The dissing of Lisp was odd given the functionality of Haskell that was used was approximately the intersection of Haskell and whichever-Lisp, plus basic static typing (which you can get in various Lisps as well: https://docs.racket-lang.org/ts-guide/ https://docs.racket-lang.org/ts-guide/ )

lolc 9y ago
Quicksort is actually O(n^2) in degenerate cases but as you note its expected to operate in-place. Proper in-place algos written in Haskell read like the imperative versions. This sort code made it into FP lore as a quicksort equivalent which it isn't. It's just neat. In this case it is not clear the author intended to claim their code has quicksort properties. The "why don't they" question at the bottom could be read as "Or is it quick-sort?" Hey I'm being generous because reading just the slides is bound to miss subtext.
- jacobparker 9y ago
  Yeah, I wasn't being very generous. However, naming the function "qsort" is pretty dishonest. I agree that the proper quick-sort implementation is going to look pretty imperative (and involve mutation) which is why I get a bit annoyed at fake-quick-sort being used to demo how pretty FP makes your code... (I agree that this implementation is neat. I think it's a great way to explain sorting.) (naive qsort is O(n^2) in the worst case (with pivot selection it is Theta(nlogn), though,) but the functional-linked-list-sort is O(n^2) in all cases... :))
qeynoluhe 9y ago
This is still an expected O(nlogn) sort though not in-place as appending only need O(n) time.
- jacobparker 9y ago
  It isn't. Perhaps you're missing the recursion (which, at each step, does two of those list appends.) Write this algorithm in an imperative language and it'll pretty clear that this is best/expected case O(n^2).
  - vilhelm_s 9y ago
    It doesn't matter that it's two list appends, 2*O(n) is still O(n). Suppose the length of (qsort (filter (<x) xs)) is k. Then the time to do the two appends in (qsort (filter (<x) xs)) ++ [x] ++ (qsort (filter (>=x) xs)) is k + (k+1), which is linear in k. At the same time any quicksort (even an in-place one) will scan through the entire array once in order to partition it, which also takes linear time. (It will take time proportional to the length of the entire array, not just the first half.) The extra work from the appends only changes the constant factors, not the asymptotics.
deleted 9y ago
[deleted]

lolc 9y ago

Quicksort is actually O(n^2) in degenerate cases but as you note its expected to operate in-place. Proper in-place algos written in Haskell read like the imperative versions. This sort code made it into FP lore as a quicksort equivalent which it isn't. It's just neat. In this case it is not clear the author intended to claim their code has quicksort properties. The "why don't they" question at the bottom could be read as "Or is it quick-sort?" Hey I'm being generous because reading just the slides is bound to miss subtext.

jacobparker 9y ago
Yeah, I wasn't being very generous. However, naming the function "qsort" is pretty dishonest. I agree that the proper quick-sort implementation is going to look pretty imperative (and involve mutation) which is why I get a bit annoyed at fake-quick-sort being used to demo how pretty FP makes your code... (I agree that this implementation is neat. I think it's a great way to explain sorting.) (naive qsort is O(n^2) in the worst case (with pivot selection it is Theta(nlogn), though,) but the functional-linked-list-sort is O(n^2) in all cases... :))

qeynoluhe 9y ago

This is still an expected O(nlogn) sort though not in-place as appending only need O(n) time.

jacobparker 9y ago
It isn't. Perhaps you're missing the recursion (which, at each step, does two of those list appends.) Write this algorithm in an imperative language and it'll pretty clear that this is best/expected case O(n^2).
- vilhelm_s 9y ago
  It doesn't matter that it's two list appends, 2*O(n) is still O(n). Suppose the length of (qsort (filter (<x) xs)) is k. Then the time to do the two appends in (qsort (filter (<x) xs)) ++ [x] ++ (qsort (filter (>=x) xs)) is k + (k+1), which is linear in k. At the same time any quicksort (even an in-place one) will scan through the entire array once in order to partition it, which also takes linear time. (It will take time proportional to the length of the entire array, not just the first half.) The extra work from the appends only changes the constant factors, not the asymptotics.

deleted 9y ago

[deleted]