3 ms·
That's amazing. Just two questions 1) on quicksort: const less = list.filter(i => i < pivot); const greater = list.filter(i => i > pivot); Wouldn'
by baby 10y ago
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?
- skidding 10y ago1) 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?
- deleted 10y ago[deleted]
- cmurphycode 10y agoI 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!