searches.median_of_medians

A Python implementation of the Median of Medians algorithm to select pivots for quick_select, which is efficient for calculating the value that would appear in the index of a list if it would be sorted, even if it is not already sorted. Search in time complexity O(n) at any rank deterministically https://en.wikipedia.org/wiki/Median_of_medians

Functions

median_of_five(→ int)	Return the median of the input list
median_of_medians(→ int)	Return a pivot to partition data on by calculating
quick_select(→ int)	Two way partition the data into smaller and greater lists,

Module Contents

searches.median_of_medians.median_of_five(arr: list) → int

Return the median of the input list :param arr: Array to find median of :return: median of arr

>>> median_of_five([2, 4, 5, 7, 899])
5
>>> median_of_five([5, 7, 899, 54, 32])
32
>>> median_of_five([5, 4, 3, 2])
4
>>> median_of_five([3, 5, 7, 10, 2])
5

searches.median_of_medians.median_of_medians(arr: list) → int

Return a pivot to partition data on by calculating Median of medians of input data :param arr: The data to be checked (a list) :return: median of medians of input array

>>> median_of_medians([2, 4, 5, 7, 899, 54, 32])
54
>>> median_of_medians([5, 7, 899, 54, 32])
32
>>> median_of_medians([5, 4, 3, 2])
4
>>> median_of_medians([3, 5, 7, 10, 2, 12])
12

searches.median_of_medians.quick_select(arr: list, target: int) → int

Two way partition the data into smaller and greater lists, in relationship to the pivot :param arr: The data to be searched (a list) :param target: The rank to be searched :return: element at rank target

>>> quick_select([2, 4, 5, 7, 899, 54, 32], 5)
32
>>> quick_select([2, 4, 5, 7, 899, 54, 32], 1)
2
>>> quick_select([5, 4, 3, 2], 2)
3
>>> quick_select([3, 5, 7, 10, 2, 12], 3)
5