Quickselect is fairly simple to understand if you already understand Quicksort. You use use a binary division but you avoid sorting sections where the order doesn't matter.

Let's start with a 7 element array

    [ 2, 4, 7, 5, 3, 6, 1 ]

We pivot on the mid-point (5) so that values less than end before it in the array and numbers larger end up after it

    [ 2, 4, 3, 1, 5, 7, 6 ]

Since 5 is now at an index greater than the midpoint, you know the median must be less than 5, so you don't care that 7 and 6 aren't sorted.

We pivot the first partition (first 4 elements) on 3 and get

   [ 2, 1, 3, 4, 5, 7, 6 ]

We don't care that 2 and 1 are unsorted, because we know that the median is > 3 (3 is at index #2 and we want index #3), so the median must be 4

▲ AdieuToLogic 2 days ago | parent [-]

And what of the likelihood that the original collection is modified when using the quickselect algorithm, thus introducing observable side effects in what could reasonably be considered a "read-only" computation?

	▲	timv 2 days ago \| parent [-]
		And there lies the tradeoffs you need to consider as part of an interview question. But if the best alternative is to sort the whole collection, then Quickselect doesn't introduce a new problem. You either accept that modifying the collection in place is an acceptable behaviour (and describe that in your API docs) or you make a copy of the collection and operate on that. Given a choice between quickselect and quicksort, quickselect will get the answer with less overhead and no additional constraints (because it's essentially the same algorithm with unnecessary steps removed). There are alternative approaches that don't require a full copy/sort, but they either require a partial copy + partial sort, or multiple passes through the collection.