> 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