Hacker News new | ask | show | jobs
by HarHarVeryFunny 265 days ago
Isn't that more of an implementation detail?

I'd guess if you care more about speed than memory it might be faster to just move elements into new array - sequence through old array appending to start/end of new array according to pivot comparison. You'd be moving every element vs leaving some in place with a swap approach, but the simplicity of the code & branch prediction might win out.
1 comments
Dan42 265 days ago
I'm pretty sure the swapping is a fundamental part of the quicksort algorithm, not a mere implementation detail. That's the reason quicksort is an in-place algorithm.
link
Dan42 265 days ago
Actually you're right, it is an implementation detail. The original isn’t mistaken, it’s just showing the lo-to-hi partitioning pass rather than the from-both-ends version I had in mind when I implemented quicksort before.

shame, shame, I should have double-checked before posting.

link