searches.median_of_medians
==========================

.. py:module:: searches.median_of_medians

.. autoapi-nested-parse::

   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
---------

.. autoapisummary::

   searches.median_of_medians.median_of_five
   searches.median_of_medians.median_of_medians
   searches.median_of_medians.quick_select


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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


.. py:function:: 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