sorts.insertion_sort
====================

.. py:module:: sorts.insertion_sort

.. autoapi-nested-parse::

   A pure Python implementation of the insertion sort algorithm

   This algorithm sorts a collection by comparing adjacent elements.
   When it finds that order is not respected, it moves the element compared
   backward until the order is correct.  It then goes back directly to the
   element's initial position resuming forward comparison.

   For doctests run following command:
   python3 -m doctest -v insertion_sort.py

   For manual testing run:
   python3 insertion_sort.py



Attributes
----------

.. autoapisummary::

   sorts.insertion_sort.T
   sorts.insertion_sort.user_input


Classes
-------

.. autoapisummary::

   sorts.insertion_sort.Comparable


Functions
---------

.. autoapisummary::

   sorts.insertion_sort.insertion_sort


Module Contents
---------------

.. py:class:: Comparable

   Bases: :py:obj:`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:
               ...


   .. py:method:: __lt__(other: Any, /) -> bool


.. py:function:: insertion_sort(collection: collections.abc.MutableSequence[T]) -> collections.abc.MutableSequence[T]

   A pure Python implementation of the insertion sort algorithm

   :param collection: some mutable ordered collection with heterogeneous
   comparable items inside
   :return: the same collection ordered by ascending

   Examples:
   >>> insertion_sort([0, 5, 3, 2, 2])
   [0, 2, 2, 3, 5]
   >>> insertion_sort([]) == sorted([])
   True
   >>> insertion_sort([-2, -5, -45]) == sorted([-2, -5, -45])
   True
   >>> insertion_sort(['d', 'a', 'b', 'e', 'c']) == sorted(['d', 'a', 'b', 'e', 'c'])
   True
   >>> import random
   >>> collection = random.sample(range(-50, 50), 100)
   >>> insertion_sort(collection) == sorted(collection)
   True
   >>> import string
   >>> collection = random.choices(string.ascii_letters + string.digits, k=100)
   >>> insertion_sort(collection) == sorted(collection)
   True


.. py:data:: T

.. py:data:: user_input