sorts.binary_insertion_sort

This is a pure Python implementation of the binary insertion sort algorithm

For doctests run following command: python -m doctest -v binary_insertion_sort.py or python3 -m doctest -v binary_insertion_sort.py

For manual testing run: python binary_insertion_sort.py

Attributes

T
user_input

Classes

Comparable

Base class for protocol classes.

Functions

binary_insertion_sort(→ list[T])

Sorts a list using the binary insertion sort algorithm.

Module Contents

class sorts.binary_insertion_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: object, /) → bool

sorts.binary_insertion_sort.binary_insertion_sort[T: Comparable](collection: list[T]) → list[T]

Sorts a list using the binary insertion sort algorithm.

Parameters:

collection – A mutable ordered collection with comparable items.

Returns:

The same collection ordered in ascending order.

Examples: >>> binary_insertion_sort([0, 4, 1234, 4, 1]) [0, 1, 4, 4, 1234] >>> binary_insertion_sort([]) == sorted([]) True >>> binary_insertion_sort([-1, -2, -3]) == sorted([-1, -2, -3]) True >>> lst = [‘d’, ‘a’, ‘b’, ‘e’, ‘c’] >>> binary_insertion_sort(lst) == sorted(lst) True >>> import random >>> collection = random.sample(range(-50, 50), 100) >>> binary_insertion_sort(collection) == sorted(collection) True >>> import string >>> collection = random.choices(string.ascii_letters + string.digits, k=100) >>> binary_insertion_sort(collection) == sorted(collection) True >>> binary_insertion_sort([1, “a”]) Traceback (most recent call last): … TypeError: ‘<’ not supported between instances of ‘str’ and ‘int’

sorts.binary_insertion_sort.T

sorts.binary_insertion_sort.user_input