What is the essence of selection algorithms?

Question

Programming

Actually, the problem and different algorithms are described here . But for the life of me, I can’t understand why they are needed at all, in terms of - what are we looking for then? Some of the elements. As an example, the search for a minimum, maximum and middle is given, but what does K have to do with it at all?

Answer 1

The task is to find the k-th element by value.
Imagine an ascending sorted list of numbers from 1 to n. You need to find the minimum - this is the first element, i.e. k = 0. You need to find the maximum element - k = n-1. You need to find the median - k \u003d n / 2 (integer division, the fractional part is simply thrown out). It seems like everything is quite simple ...
Now let's imagine that the list is not sorted, that there are duplicate elements, etc. Here... It is possible to sort the list for O(n log(n)) for example, and then to make selections on indexes. Or you can just find in O(n)...

Answer 2

We are talking about ordinal statistics - it's just an ordered sample in ascending order. Consequently, the problem is reduced to elementary sorting and selection of the element required by the score.
The maximum and minimum values ​​are given because it is obvious what places they occupy in the sorted array.