searches.quick_select

A Python implementation of the quick select algorithm, 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 https://en.wikipedia.org/wiki/Quickselect

Functions

_partition(→ tuple)	Three way partition the data into smaller, equal and greater lists,
median(items)	One common application of Quickselect is finding the median, which is
quick_select(items, index)

Module Contents

searches.quick_select._partition(data: list, pivot) → tuple

Three way partition the data into smaller, equal and greater lists, in relationship to the pivot :param data: The data to be sorted (a list) :param pivot: The value to partition the data on :return: Three list: smaller, equal and greater

searches.quick_select.median(items: list)

One common application of Quickselect is finding the median, which is the middle element (or average of the two middle elements) in a sorted dataset. It works efficiently on unsorted lists by partially sorting the data without fully sorting the entire list.

>>> median([3, 2, 2, 9, 9])
3

>>> median([2, 2, 9, 9, 9, 3])
6.0

searches.quick_select.quick_select(items: list, index: int)

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