sorts.intro_sort

Introspective Sort is a hybrid sort (Quick Sort + Heap Sort + Insertion Sort) if the size of the list is under 16, use insertion sort https://en.wikipedia.org/wiki/Introsort

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

heap_sort(→ list[T])

Sort the half-open range [start:end] in place and return the original list.

heapify(→ None)

Restore the max heap rooted at an index relative to start.

insertion_sort(→ list[T])

intro_sort(→ list[T])

median_of_3(→ T)

partition(→ int)

sort(→ list[T])

Module Contents

class sorts.intro_sort.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...
__lt__(other: Any, /) → bool
sorts.intro_sort.heap_sort[T: Comparable](array: list[T], start: int = 0, end: int | None = None) → list[T]

Sort the half-open range [start:end] in place and return the original list. If end is omitted, sort through the end of the list.

>>> heap_sort([4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12])
[1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79]
>>> heap_sort([-2, -11, 0, 0, 0, 87, 45, -69, 78, 12, 10, 103, 89, 52])
[-69, -11, -2, 0, 0, 0, 10, 12, 45, 52, 78, 87, 89, 103]
>>> heap_sort(['b', 'd', 'e', 'f', 'g', 'p', 'x', 'z', 'b', 's', 'e', 'u', 'v'])
['b', 'b', 'd', 'e', 'e', 'f', 'g', 'p', 's', 'u', 'v', 'x', 'z']
>>> heap_sort([6.2, -45.54, 8465.20, 758.56, -457.0, 0, 1, 2.879, 1.7, 11.7])
[-457.0, -45.54, 0, 1, 1.7, 2.879, 6.2, 11.7, 758.56, 8465.2]
sorts.intro_sort.heapify[T: Comparable](array: list[T], index: int, heap_size: int, start: int = 0) → None

Restore the max heap rooted at an index relative to start. heap_size is the number of elements in the heap beginning at start.

>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]
>>> heapify(array, len(array) // 2, len(array))
sorts.intro_sort.insertion_sort[T: Comparable](array: list[T], start: int = 0, end: int = 0) → list[T]
>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]
>>> insertion_sort(array, 0, len(array))
[1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79]
>>> array = [21, 15, 11, 45, -2, -11, 46]
>>> insertion_sort(array, 0, len(array))
[-11, -2, 11, 15, 21, 45, 46]
>>> array = [-2, 0, 89, 11, 48, 79, 12]
>>> insertion_sort(array, 0, len(array))
[-2, 0, 11, 12, 48, 79, 89]
>>> array = ['a', 'z', 'd', 'p', 'v', 'l', 'o', 'o']
>>> insertion_sort(array, 0, len(array))
['a', 'd', 'l', 'o', 'o', 'p', 'v', 'z']
>>> array = [73.568, 73.56, -45.03, 1.7, 0, 89.45]
>>> insertion_sort(array, 0, len(array))
[-45.03, 0, 1.7, 73.56, 73.568, 89.45]
sorts.intro_sort.intro_sort[T: Comparable](array: list[T], start: int, end: int, size_threshold: int, max_depth: int) → list[T]
>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]
>>> max_depth = 2 * math.ceil(math.log2(len(array)))
>>> intro_sort(array, 0, len(array), 16, max_depth)
[1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79]

The heap-sort fallback must preserve elements outside the requested range and return the original list, even when the depth limit is already reached.

>>> array = [100, *range(40, 0, -1), -100]
>>> expected = [100, *range(1, 41), -100]
>>> result = intro_sort(array, 1, 41, 16, 0)
>>> result is array
True
>>> result == expected
True

The same boundaries must be respected when the fallback occurs after a partition.

>>> array = [100, *range(40, 0, -1), -100]
>>> result = intro_sort(array, 1, 41, 16, 1)
>>> result is array
True
>>> result == expected
True
sorts.intro_sort.median_of_3[T: Comparable](array: list[T], first_index: int, middle_index: int, last_index: int) → T
>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]
>>> median_of_3(array, 0, ((len(array) - 0) // 2) + 1, len(array) - 1)
12
>>> array = [13, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]
>>> median_of_3(array, 0, ((len(array) - 0) // 2) + 1, len(array) - 1)
13
>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 15, 14, 27, 79, 23, 45, 14, 16]
>>> median_of_3(array, 0, ((len(array) - 0) // 2) + 1, len(array) - 1)
14
sorts.intro_sort.partition[T: Comparable](array: list[T], low: int, high: int, pivot: T) → int
>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]
>>> partition(array, 0, len(array), 12)
8
>>> array = [21, 15, 11, 45, -2, -11, 46]
>>> partition(array, 0, len(array), 15)
3
>>> array = ['a', 'z', 'd', 'p', 'v', 'l', 'o', 'o']
>>> partition(array, 0, len(array), 'p')
5
>>> array = [6.2, -45.54, 8465.20, 758.56, -457.0, 0, 1, 2.879, 1.7, 11.7]
>>> partition(array, 0, len(array), 2.879)
6
sorts.intro_sort.sort[T: Comparable](array: list[T]) → list[T]
Parameters:

collection – some mutable ordered collection with heterogeneous

comparable items inside :return: the same collection ordered by ascending

Examples: >>> sort([4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12]) [1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79] >>> sort([-1, -5, -3, -13, -44]) [-44, -13, -5, -3, -1] >>> sort([]) [] >>> sort([5]) [5] >>> sort([-3, 0, -7, 6, 23, -34]) [-34, -7, -3, 0, 6, 23] >>> sort([1.7, 1.0, 3.3, 2.1, 0.3 ]) [0.3, 1.0, 1.7, 2.1, 3.3] >>> sort([‘d’, ‘a’, ‘b’, ‘e’, ‘c’]) [‘a’, ‘b’, ‘c’, ‘d’, ‘e’] >>> sort([1, ‘a’]) # doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last): … TypeError: …

sorts.intro_sort.user_input