Quick Select Clarification

Question

What is exactly meant by "k" in this lecture slide of Quick Select?

Answer 1

Let's say you took a number x.

Let L be the set of numbers less than x in the array, size of the set is |L|

Let E be the set of numbers equal to x in the array, size of the set is |E|

Let G be the set of numbers larger than x in the array, size of the set is |G|

Let's imagine the sorted array, the first |L| numbers (1 -> |L|) are contained in set L.

The following |E| numbers (|L|+1 -> |L|+|E|) are contained in set E.

The following |G| numbers (|L|+|E|+1 -> end) are contained in set G.

We are looking for the kth smallest number, so we have 3 cases:

1) k <= |L| this means that the number we are looking for is in the first |L| numbers in the sorted array, so we search for the kth smallest number in L.

2) |L| < k <= |L|+|E| this means that the number we are looking for is in a position between (|L|+1 -> |L|+|E|) in the sorted array, so it is an element from E. Since all elements of E are equal to x, we know that the kth smallest number is equal to x.

3) k > |L|+|E| this means that the number we are looking for is in a position between (|L|+|E|+1 -> end) in the sorted array, so it is an element from 'G'. Since there are already |L|+|E| numbers less than the kth smallest number, we can subtract |L|+|E| from k, let's call it k' (k' = k - |L| - |E|), and search for the k'th smallest element in G.