3 ms·
How does one determine the median wherein "the other numbers can be unsorted"? To wit, given the unordered set: [ 5, 1, 3 ] How would "Only the median (or
by AdieuToLogic 3mo ago
How does one determine the median wherein "the other numbers can be unsorted"?
To wit, given the unordered set:
[ 5, 1, 3 ]
How would "Only the median (or pair around the median) needs to be sorted" be satisfied?
- salamanderman 3mo agohttps://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect
- AdieuToLogic 3mo agoFrom the Wikipedia page cited: As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the kth element, it also partially sorts the data. When the above is applicable, those quickselect implementations would violate the original assertion of: Only the median (or pair around the median) needs to be sorted, the other numbers can be unsorted When the collection involved is immutable.