sorts.shrink_shell_sort

This function implements the shell sort algorithm which is slightly faster than its pure implementation.

This shell sort is implemented using a gap, which shrinks by a certain factor each iteration. In this implementation, the gap is initially set to the length of the collection. The gap is then reduced by a certain factor (1.3) each iteration.

For each iteration, the algorithm compares elements that are a certain number of positions apart (determined by the gap). If the element at the higher position is greater than the element at the lower position, the two elements are swapped. The process is repeated until the gap is equal to 1.

The reason this is more efficient is that it reduces the number of comparisons that need to be made. By using a smaller gap, the list is sorted more quickly.

Classes

Comparable

Base class for protocol classes.

Functions

shell_sort(→ list[T])

Implementation of shell sort algorithm in Python

Module Contents

class sorts.shrink_shell_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.shrink_shell_sort.shell_sort[T: Comparable](collection: list[T]) → list[T]

Implementation of shell sort algorithm in Python :param collection: Some mutable ordered collection with heterogeneous comparable items inside :return: the same collection ordered by ascending

>>> shell_sort([3, 2, 1])
[1, 2, 3]
>>> shell_sort([])
[]
>>> shell_sort([1])
[1]
>>> shell_sort(["pear", "apple", "orange"])
['apple', 'orange', 'pear']
>>> shell_sort([2.5, -1, 0.0])
[-1, 0.0, 2.5]
>>> shell_sort([1, "a"])
Traceback (most recent call last):
    ...
TypeError: ...