sorts.recursive_insertion_sort

A recursive implementation of the insertion sort algorithm

Attributes

T
numbers

Classes

Comparable

Base class for protocol classes.

Functions

insert_next(→ None)	Inserts the '(index-1)th' element into place
rec_insertion_sort(→ None)	Given a collection of comparable elements and its length, sorts the

Module Contents

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

sorts.recursive_insertion_sort.insert_next[T](collection: collections.abc.MutableSequence[T], index: int) → None

Inserts the ‘(index-1)th’ element into place

>>> col = [3, 2, 4, 2]
>>> insert_next(col, 1)
>>> col
[2, 3, 4, 2]

>>> col = [3, 2, 3]
>>> insert_next(col, 2)
>>> col
[3, 2, 3]

>>> col = []
>>> insert_next(col, 1)
>>> col
[]

sorts.recursive_insertion_sort.rec_insertion_sort[T](collection: collections.abc.MutableSequence[T], n: int) → None

Given a collection of comparable elements and its length, sorts the collection in place in ascending order.

Parameters:

• collection – A mutable collection of comparable elements

• n – The length of collection

>>> col = [1, 2, 1]
>>> rec_insertion_sort(col, len(col))
>>> col
[1, 1, 2]

>>> col = [2, 1, 0, -1, -2]
>>> rec_insertion_sort(col, len(col))
>>> col
[-2, -1, 0, 1, 2]

>>> col = [1]
>>> rec_insertion_sort(col, len(col))
>>> col
[1]

>>> col = ['d', 'a', 'b', 'e', 'c']
>>> rec_insertion_sort(col, len(col))
>>> col
['a', 'b', 'c', 'd', 'e']

sorts.recursive_insertion_sort.T

sorts.recursive_insertion_sort.numbers