sorts.recursive_quick_sort

A pure Python implementation of a recursive quick sort.

For doctests run the following command:

python3 -m doctest -v recursive_quick_sort.py

For manual testing run:

python3 recursive_quick_sort.py

Classes

Comparable

Base class for protocol classes.

Functions

quick_sort(→ list[T])

Sort a list of mutually comparable items with recursive quick sort.

Module Contents

class sorts.recursive_quick_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:
        ...

__ge__(other: Any, /) → bool

__le__(other: Any, /) → bool

sorts.recursive_quick_sort.quick_sort[T: Comparable](data: list[T]) → list[T]

Sort a list of mutually comparable items with recursive quick sort.

Returns a new list. Items must be mutually orderable. Mixing types that cannot be compared raises TypeError instead of returning a silently wrong order.

Examples: >>> quick_sort([2, 1, 0]) [0, 1, 2] >>> quick_sort([2.2, 1.1, 0]) [0, 1.1, 2.2] >>> quick_sort([“c”, “a”, “b”]) [‘a’, ‘b’, ‘c’] >>> quick_sort([]) [] >>> quick_sort([0]) [0] >>> quick_sort([2.5, -1, 0.0]) == sorted([2.5, -1, 0.0]) True >>> quick_sort(list(“quick_sort”)) == sorted(“quick_sort”) True >>> quick_sort([1, “a”]) Traceback (most recent call last):

…

TypeError: ‘<=’ not supported between instances of ‘str’ and ‘int’ >>> for data in ([2, 1, 0], [2.2, 1.1, 0], list(“quick_sort”)): … quick_sort(data) == sorted(data) True True True