<commit_before>.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata:: Insertion Sort
   :author: <NAME>
   :prerequisites: Sorting
   :topic: Sorting
   :short_name: InsertionSort

.. _InsertionSort:

.. index:: ! Insertion Sort

.. include:: JSAVheader.rinc

.. odsalink:: AV/Sorting/quadraticsortCON.css

Insertion Sort
==============

What if you have a stack of phone bills from the past two years
and you want to organize them by date?
A fairly natural way to do this might be to look at the first two
bills and put them in order.
Then take the third bill and put it into the right order with respect
to the first two, and so on.
As you take each bill, you would add it to the sorted pile that you
have already made.
This natural approach to sorting is the inspiration for
our first sorting algorithm, called :dfn:`Insertion Sort`.

Insertion Sort iterates through a list of records.
For each iteration, the current record is inserted in turn at the
correct position within a sorted list composed of those records
already processed.
Here is an implementation.
The input is an array of :math:`n` records stored in array ``A``.<commit_msg>Example of module with list of exercises used to check module proficiency<commit_after>.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata:: Insertion Sort
   :author: <NAME>
   :prerequisites: Sorting
   :topic: Sorting
   :short_name: InsertionSort
   :exercises: InssortCON1, InssortCON2, InssortCON3, InssortSumm, InssortPRO  

.. _InsertionSort:

.. index:: ! Insertion Sort

.. include:: JSAVheader.rinc

.. odsalink:: AV/Sorting/quadraticsortCON.css

Insertion Sort
==============

What if you have a stack of phone bills from the past two years
and you want to organize them by date?
A fairly natural way to do this might be to look at the first two
bills and put them in order.
Then take the third bill and put it into the right order with respect
to the first two, and so on.
As you take each bill, you would add it to the sorted pile that you
have already made.
This natural approach to sorting is the inspiration for
our first sorting algorithm, called :dfn:`Insertion Sort`.

Insertion Sort iterates through a list of records.
For each iteration, the current record is inserted in turn at the
correct position within a sorted list composed of those records
already processed.
Here is an implementation.
The input is an array of :math:`n` records stored in array ``A``.
{'fraction_non_alphanumeric': 0.07035175879396985, 'fraction_numerical': 0.003948312993539124, 'mean_word_length': 4.058076225045372, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5188625', 'n_tokens_mistral': 783, 'n_tokens_neox': 763, 'n_words': 412}