Getting Started with Your First Contribution to TheAlgorithms/Python

#### What is an Algorithm?

An Algorithm is one or more functions (or classes) that:
* take one or more inputs,
* perform some internal calculations or data manipulations,
* return one or more outputs,
* have minimal side effects (Ex. `print()`, `plot()`, `read()`, `write()`).

Algorithms should be packaged in a way that would make it easy for readers to put them into larger programs.

Algorithms should:
* have intuitive class and function names that make their purpose clear to readers
* use Python naming conventions and intuitive variable names to ease comprehension
* be flexible to take different input values
* have Python type hints for their input parameters and return values
* raise Python exceptions (`ValueError`, etc.) on erroneous input values
* have docstrings with clear explanations and/or URLs to source materials
* contain doctests that test both valid and erroneous input values
* return all calculation results instead of printing or plotting them

Algorithms in this repo should not be how-to examples for existing Python packages. Instead, they should perform internal calculations or manipulations to convert input values into different output values. Those calculations or manipulations can use data types, classes, or functions of existing Python packages but each algorithm in this repo should add unique value.

"""
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
"""

from collections.abc import MutableSequence
from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
    def __lt__(self, other: Any, /) -> bool: ...


T = TypeVar("T", bound=Comparable)


def insertion_sort[T: Comparable](collection: MutableSequence[T]) -> 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
    """

    for insert_index in range(1, len(collection)):
        insert_value = collection[insert_index]
        while insert_index > 0 and insert_value < collection[insert_index - 1]:
            collection[insert_index] = collection[insert_index - 1]
            insert_index -= 1
        collection[insert_index] = insert_value
    return collection


if __name__ == "__main__":
    from doctest import testmod

    testmod()

    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(f"{insertion_sort(unsorted) = }")

## Audio Filters
  * [Butterworth Filter](audio_filters/butterworth_filter.py)
  * [Iir Filter](audio_filters/iir_filter.py)
  * [Show Response](audio_filters/show_response.py)

## Backtracking
  * [All Combinations](backtracking/all_combinations.py)
  * [All Permutations](backtracking/all_permutations.py)
  * [All Subsequences](backtracking/all_subsequences.py)
  * [Coloring](backtracking/coloring.py)
  * [Combination Sum](backtracking/combination_sum.py)
  * [Crossword Puzzle Solver](backtracking/crossword_puzzle_solver.py)
  * [Generate Parentheses](backtracking/generate_parentheses.py)
  * [Generate Parentheses Iterative](backtracking/generate_parentheses_iterative.py)
  * [Hamiltonian Cycle](backtracking/hamiltonian_cycle.py)
  * [Knight Tour](backtracking/knight_tour.py)
  * [Match Word Pattern](backtracking/match_word_pattern.py)
  * [Minimax](backtracking/minimax.py)
  * [N Queens](backtracking/n_queens.py)
  * [N Queens Math](backtracking/n_queens_math.py)
  * [Power Sum](backtracking/power_sum.py)
  * [Rat In Maze](backtracking/rat_in_maze.py)
  * [Sudoku](backtracking/sudoku.py)
  * [Sum Of Subsets](backtracking/sum_of_subsets.py)
  * [Word Break](backtracking/word_break.py)
  * [Word Ladder](backtracking/word_ladder.py)
  * [Word Search](backtracking/word_search.py)

[tool.pytest]
ini_options.markers = [
  "mat_ops: mark a test as utilizing matrix operations.",
]
ini_options.addopts = [
  "--durations=10",
  "--doctest-modules",
  "--showlocals",
]

#### Other Requirements for Submissions
- If you are submitting code in the `project_euler/` directory, please also read [the dedicated Guideline](https://github.com/TheAlgorithms/Python/blob/master/project_euler/README.md) before contributing to our Project Euler library.
- The file extension for code files should be `.py`. Jupyter Notebooks should be submitted to [TheAlgorithms/Jupyter](https://github.com/TheAlgorithms/Jupyter).
- Strictly use snake_case (underscore_separated) in your file_name, as it will be easy to parse in future using scripts.
- Please avoid creating new directories if at all possible. Try to fit your work into the existing directory structure.
- If possible, follow the standard *within* the folder you are submitting to.
- If you have modified/added code work, make sure the code compiles before submitting.
- If you have modified/added documentation work, ensure your language is concise and contains no grammar errors.
- Do not update the README.md or DIRECTORY.md file which will be periodically autogenerated by our GitHub Actions processes.
- Add a corresponding explanation to [Algorithms-Explanation](https://github.com/TheAlgorithms/Algorithms-Explanation) (Optional but recommended).
- All submissions will be tested with [__mypy__](http://www.mypy-lang.org) so we encourage you to add [__Python type hints__](https://docs.python.org/3/library/typing.html) where it makes sense to do so.

- Most importantly,
  - __Be consistent in the use of these guidelines when submitting.__
  - __Join__ us on [Discord](https://discord.com/invite/c7MnfGFGa6) and [Gitter](https://gitter.im/TheAlgorithms/community) __now!__
  - Happy coding!

Writer [@poyea](https://github.com/poyea), Jun 2019.