|
|
|
|
|
|
by AdieuToLogic
20 days ago
|
|
|
> You can definitely do this without sorting. > QuickSelect is ... Quickselect implementations can, and often do, partially sort the underlying collection: As with quicksort, quickselect is generally implemented as
an in-place algorithm, and beyond selecting the kth
element, it also partially sorts the data.[0]
If you are aware of a quickselect implementation having O(n) average performance which does not modify the underlying collection, I would very much appreciate a reference to same.0 - https://en.wikipedia.org/wiki/Quickselect |
|
|