Hands-On Data Structures and Algorithms with Python - Second Edition

Pivot selection

To implement the deterministic algorithm to efficiently determine the i^th smallest value from the list, we start by implementing the pivot selection method. Previously, in the random selection algorithm, we selected the first element as the pivot. We shall replace that step with a sequence of steps that enables us to obtain the approximate median. This will improve the partitioning of the list regarding the pivot:

    def partition(unsorted_array, first_index, last_index):         if first_index == last_index:             return first_index         else:             nearest_median =                 median_of_medians(unsorted_array[first_index:last_index])         index_of_nearest_median =             get_index_of_nearest_median(unsorted_array, first_index,                                         last_index, nearest_median)  swap(unsorted_array, ...