Hacker News Reader

Comment by baby | Hacker News Reader

That's amazing. Just two questions

1) on quicksort:

    const less = list.filter(i => i < pivot);
    const greater = list.filter(i => i > pivot);

Wouldn't this be faster:

    less    = what's < pivot
    greater = the rest

2) What is the algorithm people use?

View on HN

I may not have parsed your question correctly, so I apologize in advance. Assuming you are asking about what happens to the "equal" elements-

Yes, there is a bug in this code. It doesn't handle repeated elements.

If you fix the code by including an equality in one of the two groups, then it works, but it degrades when there are many repeated elements. In the worst case, you can only shrink your groups by one each time, which means the complexity changes to O(n^2) :(

You can fix THIS issue using a 3-way partition. That is the algorithm I've used. With a good pivot choice (random or median of three), this gives you an in-place sort which is guaranteed to be O(nlgn). Nice!

1) It's written in a functional way where you don't mutate the initial list. Edit: I guess you could iterate once and populate both left and right sides at the same time, but that would make the code more verbose (personal bias).

2) What do you mean?

2) Isn't one of these sorting algorithm faster than the other? The complexity of this one is n*log(n) right?

In the average case, yes, but it depends on the pivot strategy.

Reply on news.ycombinator.com