What does kth largest/smallest element mean?

Question

I'm currently studying selection algorithms, namely, median of medians.

I came across two following sentences:

In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array;

In computer science, the median of medians is an approximate (median) selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, mainly the quickselect, that selects the kth largest element of an initially unsorted array.

What does kth smallest/largest element mean? To make question a bit more concrete, consider following (unsorted) array:

[19, 1, 7, 20, 8, 10, 19, 24, 23, 6]

For example, what is 5th smallest element? And what is 5th largest element?

If you sort the array from smallest to largest, the 5th smallest element is the 5th element in the sorted array. The 5th largest element is the 5th from the end in the sorted array. 10 is the fifth smallest, 19 is the fifth largest. — alkasm
Was the question just wanting to clarify what "kth" meant in that context? — Shaun Sweet

alkasm alkasm · Accepted Answer · 2019-07-25T20:15:02

If you sort the array from smallest to largest, the kth smallest element is the kth element in the sorted array. The kth largest element is the kth from the end in the sorted array. Let's examine your example array in Python:

In [2]: sorted([19, 1, 7, 20, 8, 10, 19, 24, 23, 6])
Out[2]: [1, 6, 7, 8, 10, 19, 19, 20, 23, 24]

The smallest element is 1, second smallest is 6, and so on. So the kth smallest is the kth element from the left. Similarly, 24 is the largest, 23 the second largest, and so on, so the kth largest element is the kth element from the right. So if k = 5:

In [3]: sorted([19, 1, 7, 20, 8, 10, 19, 24, 23, 6])[4]  # index 4 is 5th from the start
Out[3]: 10

In [4]: sorted([19, 1, 7, 20, 8, 10, 19, 24, 23, 6])[-5] # index -5 is 5th from the end
Out[4]: 19

Note that you don't have to sort the array in order to get the kth smallest/largest value. Sorting is just an easy way to see which value corresponds to k.

What does kth largest/smallest element mean?

1 Answers