Getting the kth largest elemtent with quick select

Question

I have written some python code that gets the Kth smallest element in an unsorted array. I'll like to get help to reverse the function to get the Kth largest element. I know that there are other questions on StackOverflow that answer this, but honestly, I'm not here because I want my question answered. I'm here because I want the pattern, how to think about problems like these, so that the next time I see a question like this I would be able to answer. So please explain clearly to me and help me to really understand what to do so that I can do similar problems in the future.

from typing import List


def partition(array: List[int], lowerbound: int, upperbound: int) -> int:
    """
    Partitions the array so that lower items are to the left of the pivot and bigger items are to the right.
    """
    pivot = array[upperbound]
    index_1 = lowerbound - 1

    for index_2 in range(lowerbound, upperbound):  # we loop from lowerbound and stop just before the pivot.
        if array[index_2] < pivot:  # if the value at index 2 is less than the pivot.
            index_1 += 1
            array[index_1], array[index_2] = array[index_2], array[index_1]  # swap index one and two
    array[index_1 + 1], array[upperbound] = array[upperbound], array[index_1 + 1]
    return index_1 + 1  # return the pivot(basically it's index)


def quick_select(array: List[int], lowerbound: int, upperbound: int, item_index: int) -> int:
    """
    Performs the quick select algorithm.
    """
    if lowerbound >= upperbound:
        return array[lowerbound]

    pivot_index = partition(array, lowerbound, upperbound)
    if pivot_index == item_index:
        return array[item_index]

    if pivot_index > item_index:
        return quick_select(array, lowerbound, pivot_index - 1, item_index)
    else:
        return quick_select(array, pivot_index + 1, upperbound, item_index)
    ```

Answer 1

There are at least two ways:

• The Kth largest is the (N+1-K)th smallest, and you don't even need to rewrite the algorithm.

• In the given code, wherever there is an element comparison, flip its direction (turn > to <, >= to <= and so on). Caution: I mean element comparisons only.

---

Yet another option is to change the sign of all elements in the array, look for the smallest and restore the sign.

I would not recommend this method, unless the change of sign is done virtually, i.e. assumed in the statements that involve the elements. E.g. a > b is rewritten -a > -b, which is also a < b, and that brings us back to the second method.