algorithmselectquickselect

Quick Select Clarification


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

enter image description here


Solution

  • 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.