cs_survival_kit.algorithms.sorting ¶

Bases: Protocol

A sequence a sort can rearrange in place: readable and writable by index.

This is the smallest contract a comparison sort can be written against. Three operations, all by position: len(items), items[i] and items[i] = x. Nothing is inserted or removed, because sorting never changes which elements are present, only where they are.

The built-in list satisfies it. So does every AbstractList in the kit, which is the point: the same sort runs on a DynamicArray and a SinglyLinkedList, and the difference in what it costs comes entirely from what items[i] costs on each.

Indices are non-negative positions, 0 <= i < len(items), as they are for AbstractList. A sort never uses negative indices or slices.

Examples:

The protocol is checked structurally. Lists and the kit's own lists satisfy it; a tuple does not, because it cannot be written to:

>>> from cs_survival_kit.data_structures import DynamicArray
>>> isinstance([3, 1, 2], Sortable), isinstance(DynamicArray[int](), Sortable)
(True, True)
>>> isinstance((3, 1, 2), Sortable)
False

__len__() -> int

82
83
84

def __len__(self) -> int:
    """Return the number of elements."""
    ...

__getitem__(index: int) -> T

86
87
88

def __getitem__(self, index: int, /) -> T:
    """Return the element at `index`."""
    ...

__setitem__(index: int, item: T) -> None

90
91
92

def __setitem__(self, index: int, item: T, /) -> None:
    """Replace the element at `index` with `item`."""
    ...

Bases: Protocol

The signature every sort in the kit has.

A sort is a function, not a class, because it keeps no state between calls. It takes the sequence as its only positional argument and rearranges it in place, returning nothing, like list.sort. The two keyword arguments are the built-in's, with the built-in's meaning:

• key maps each element to the value to compare. Without it, the elements are compared directly and must support <.
• reverse=True sorts descending. A stable sort stays stable: elements that compare equal keep their original order, in either direction.

Writing the contract down means a benchmark can run every sort on the same input, a test suite can check every sort against the same reference, and a caller can swap one sort for another by changing one name.

Examples:

Any function with the signature satisfies it. A wrapper around the built-in is the reference the kit's sorts are tested against:

>>> def builtin_sort(items, /, *, key=None, reverse=False):
...     for i, item in enumerate(sorted(items, key=key, reverse=reverse)):
...         items[i] = item
>>> sorter: SortAlgorithm = builtin_sort
>>> a = [3, 1, 2]
>>> sorter(a, reverse=True)
>>> a
[3, 2, 1]

Switching to a sort from the kit is a change of name:

>>> from cs_survival_kit.algorithms.sorting import insertion_sort
>>> sorter = insertion_sort

__call__(items: Sortable[T], /, *, key: Callable[[T], SupportsLessThan] | None = None, reverse: bool = False) -> None

139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

def __call__[T](
    self,
    items: Sortable[T],
    /,
    *,
    key: Callable[[T], SupportsLessThan] | None = None,
    reverse: bool = False,
) -> None:
    """Sort `items` in place.

    Args:
        items: The sequence to sort. It is rearranged; nothing is added
            or removed.
        key: A function of one element returning the value to compare.
            `None` compares the elements themselves.
        reverse: If true, sort in descending order.
    """
    ...

Bases: Protocol

Anything that can be compared with <.

A comparison sort needs exactly one question answered about its elements: is this one less than that one? Numbers, strings, tuples and anything else with __lt__ can answer it. A key function maps each element to something that can.

__lt__(other: Any) -> bool

34
35
36

def __lt__(self, other: Any, /) -> bool:
    """Return whether this value sorts before `other`."""
    ...