Python Data Structures and Algorithms

Pivot selection

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 true or approximate median. This will improve the partitioning of the list about 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, first_index, index_of_nearest_median)         pivot = unsorted_array[first_index]         pivot_index = first_index  index_of_last_element = last_index  ...