Suggest edit — insertion sort

Title

Name

Note

---
title: "insertion sort"
type: concept
related: [Loop Invariant, Insertion Sort, Keys]
source: https://www.jemoka.com/posts/kbhinsertion_sort/
confidence: high
status: active
---

insertion sort is an algorithm that solves the sorting problem.
constituents a sequence of \(n\) numbers \(\{a_1, \dots a_{n}\}\), called keys
intuition Say you have a sorted list; sticking a new element into the list doesn&rsquo;t change the fact that the list is sorted.
requirements Insertion sort provides an ordered sequence \(\{a_1&rsquo;, \dots a_{n}&rsquo;\}\) s.t. \(a_1&rsquo; \leq \dots \leq a_{n}&rsquo;\)
void insertion_sort(int length, int *A) { for (int j=1; j&lt;length; j++) { int key = A[j]; // insert the key correctly into the // sorted sequence, when appropriate int i = j-1; while (i &gt; 0 &amp;&amp; A[i] &gt; key) { // if things before had // larger key // move them A[i+1] = A[i]; // move it down // move our current value down i -= 1; } // put our new element into the correct palace A[i+1] = key; } } This is an \(O\qty(n^{2})\) algorithm.
additional information proof After iteration \(i\) of the outer loop, \(A[:i+1]\) is sorted.
Base case: after iteration \(0\), the list \(A[:1]\) (i.e. list of one element) is sorted.
For any \(0 &lt; k &lt; n\), the inductive hypothesis holds for \(i=k-1\), then it holds for \(i=k\) because we are sticking the list into before the smallest element bigger than the main element.
The inductive hypothesis holds or all \(i = 0 \ldots n-1\), that would tell us via the inductive hypothesis the list \(A[:n]\) is sorted.
proof We use loop invariant method to show that our algorithm is correct. Our invariant is that the array \(A[0, \dots, j-1]\) is sorted \(\forall j 0 \dots L+1\).
Initialization: at the first step, \(j=1\) (second element), the subarray of \(A[0, \dots j-1]\) (namely, only the first element), is sorted trivially Maintenance: during each loop, we move \(j\) to the right, only being done when the subarray to the left is correctly sorted because of \(j\) is moving forward until length, it will terminate As \(j\), by the end, covers the entire loop, our loop terminates at \(L+1\) and invariant (sortedness) is maintained between \(A[0, \dots j]\).