Re:Lomuto's Comeback
by loeg on Sunday May 17, 2020 @01:59PM
(#23213775)
> Then again, maybe there are algorithms letting you compute percentiles without sorting?
I think you may be able to do so probabilistically, which is often good enough? Additionally, one observation about percentiles is that you don't need to sort all of the data; you can just hold on to the top N results in something like a Heap.
I think you may be able to do so probabilistically, which is often good enough? Additionally, one observation about percentiles is that you don't need to sort all of the data; you can just hold on to the top N results in something like a Heap.