Python Data Structures and Algorithms

Quick select

The quick select algorithm is used to obtain the ith-smallest element in an unordered list of items, in this case, numbers. We declare the main method of the algorithm as follows:

    def quick_select(array_list, left, right, k):         split = partition(array_list, left, right)         if split == k:             return array_list[split]         elif split < k:             return quick_select(array_list, split + 1, right, k)         else:             return quick_select(array_list, left, split-1, k) 

The quick_select function takes as parameters the index of the first element in the list as well as the last. The ith element is specified by the third parameter k. Values greater or equal to zero (0) are allowed in such a way that when k is 0, we know to search for the first-smallest item in ...