Welcome to quickselect’s documentation!
Note
If object is not listed in documentation it should be considered as implementation detail that can change and should not be relied upon.
floyd_rivest module
Based on selection algorithm by Robert W. Floyd and Ronald L. Rivest.
- quickselect.floyd_rivest.nth_largest(sequence: MutableSequence[Domain], n: int, *, key: Callable[[Domain], Any] | None = None) Domain [source]
Returns n-th largest element and partially sorts given sequence while searching.
complexity
best
average
worst
time
O(size)
O(size)
O(size ** 2)
memory
O(1)
O(log size)
O(size)
where
size = len(sequence)
.- Parameters:
sequence – sequence to search in
n – index of the element to search for in the sequence sorted by key in descending order (e.g.
n = 0
corresponds to the maximum element)key – single argument ordering function, if none is specified compares elements themselves
- Returns:
n-th largest element of the sequence
>>> sequence = list(range(-10, 11)) >>> nth_largest(sequence, 0) 10 >>> nth_largest(sequence, 1) 9 >>> nth_largest(sequence, 19) -9 >>> nth_largest(sequence, 20) -10 >>> nth_largest(sequence, 0, key=abs) -10 >>> nth_largest(sequence, 1, key=abs) -10 >>> nth_largest(sequence, 19, key=abs) -1 >>> nth_largest(sequence, 20, key=abs) 0
- quickselect.floyd_rivest.nth_smallest(sequence: MutableSequence[Domain], n: int, *, key: Callable[[Domain], Any] | None = None) Domain [source]
Returns n-th smallest element and partially sorts given sequence while searching.
complexity
best
average
worst
time
O(size)
O(size)
O(size ** 2)
memory
O(1)
O(log size)
O(size)
where
size = len(sequence)
.- Parameters:
sequence – sequence to search in
n – index of the element to search for in the sequence sorted by key in ascending order (e.g.
n = 0
corresponds to the minimum element)key – single argument ordering function, if none is specified compares elements themselves
- Returns:
the n-th smallest element of the sequence
>>> sequence = list(range(-10, 11)) >>> nth_smallest(sequence, 0) -10 >>> nth_smallest(sequence, 1) -9 >>> nth_smallest(sequence, 19) 9 >>> nth_smallest(sequence, 20) 10 >>> nth_smallest(sequence, 0, key=abs) 0 >>> nth_smallest(sequence, 1, key=abs) -1 >>> nth_smallest(sequence, 19, key=abs) -10 >>> nth_smallest(sequence, 20, key=abs) 10
- quickselect.floyd_rivest.select(sequence: MutableSequence[Domain], n: int, *, start: int = 0, stop: int | None = None, key: Callable[[Domain], Any] | None = None, comparator: Callable[[Any, Any], bool]) Domain [source]
Partially sorts given sequence and returns n-th element.
complexity
best
average
worst
time
O(size)
O(size)
O(size ** 2)
memory
O(1)
O(log size)
O(size)
where
size = len(sequence)
.- Parameters:
sequence – sequence to select from
n – index of the element to select
start – index to start selection from
stop – index to stop selection at
key – single argument ordering function, if none is specified compares elements themselves
comparator – binary predicate that defines the sorting order
- Returns:
n-th element of the sequence with slice partially sorted by key in given order
>>> from operator import gt, lt >>> sequence = list(range(-10, 11)) >>> select(sequence, 0, stop=5, comparator=gt) -5 >>> select(sequence, 0, stop=5, comparator=lt) -10 >>> select(sequence, 20, start=15, comparator=lt) 10 >>> select(sequence, 20, start=15, comparator=gt) 5 >>> select(sequence, 5, start=5, stop=15, key=abs, comparator=lt) 0 >>> select(sequence, 5, start=5, stop=15, key=abs, comparator=gt) 10
hoare module
Based on “quickselect” selection algorithm by Tony Hoare.
- quickselect.hoare.nth_largest(sequence: MutableSequence[Domain], n: int, *, key: Callable[[Domain], Any] | None = None) Domain [source]
Returns n-th largest element and partially sorts given sequence while searching.
complexity
best
average
worst
time
O(size)
O(size)
O(size ** 2)
memory
O(1)
O(log size)
O(size)
where
size = len(sequence)
.- Parameters:
sequence – sequence to search in
n – index of the element to search for in the sequence sorted by key in descending order (e.g.
n = 0
corresponds to the maximum element)key – single argument ordering function, if none is specified compares elements themselves
- Returns:
n-th largest element of the sequence
>>> sequence = list(range(-10, 11)) >>> nth_largest(sequence, 0) 10 >>> nth_largest(sequence, 1) 9 >>> nth_largest(sequence, 19) -9 >>> nth_largest(sequence, 20) -10 >>> nth_largest(sequence, 0, key=abs) 10 >>> nth_largest(sequence, 1, key=abs) -10 >>> nth_largest(sequence, 19, key=abs) 1 >>> nth_largest(sequence, 20, key=abs) 0
- quickselect.hoare.nth_smallest(sequence: MutableSequence[Domain], n: int, *, key: Callable[[Domain], Any] | None = None) Domain [source]
Returns n-th smallest element and partially sorts given sequence while searching.
complexity
best
average
worst
time
O(size)
O(size)
O(size ** 2)
memory
O(1)
O(log size)
O(size)
where
size = len(sequence)
.- Parameters:
sequence – sequence to search in
n – index of the element to search for in the sequence sorted by key in ascending order (e.g.
n = 0
corresponds to the minimum element)key – single argument ordering function, if none is specified compares elements themselves
- Returns:
n-th smallest element of the sequence
>>> sequence = list(range(-10, 11)) >>> nth_smallest(sequence, 0) -10 >>> nth_smallest(sequence, 1) -9 >>> nth_smallest(sequence, 19) 9 >>> nth_smallest(sequence, 20) 10 >>> nth_smallest(sequence, 0, key=abs) 0 >>> nth_smallest(sequence, 1, key=abs) 1 >>> nth_smallest(sequence, 19, key=abs) -10 >>> nth_smallest(sequence, 20, key=abs) 10
- quickselect.hoare.select(sequence: MutableSequence[Domain], n: int, *, start: int = 0, stop: int | None = None, key: Callable[[Domain], Any] | None = None, comparator: Callable[[Any, Any], bool]) Domain [source]
Partially sorts given sequence and returns n-th element.
complexity
best
average
worst
time
O(size)
O(size)
O(size ** 2)
memory
O(1)
O(log size)
O(size)
where
size = len(sequence)
.- Parameters:
sequence – sequence to select from
n – index of the element to select
start – index to start selection from
stop – index to stop selection at
key – single argument ordering function, if none is specified compares elements themselves
comparator – binary predicate that defines the sorting order
- Returns:
n-th element of the sequence with slice partially sorted by key in given order
>>> from operator import gt, lt >>> sequence = list(range(-10, 11)) >>> select(sequence, 0, stop=5, comparator=gt) -5 >>> select(sequence, 0, stop=5, comparator=lt) -10 >>> select(sequence, 20, start=15, comparator=lt) 10 >>> select(sequence, 20, start=15, comparator=gt) 5 >>> select(sequence, 5, start=5, stop=15, key=abs, comparator=lt) 0 >>> select(sequence, 5, start=5, stop=15, key=abs, comparator=gt) 10