From 8868869969165aad158fcdd4b9f3e05866282395 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 11 Sep 2021 14:56:21 -0600 Subject: add notes on insertion sort --- notes.md | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) diff --git a/notes.md b/notes.md index b474a52..17129e5 100644 --- a/notes.md +++ b/notes.md @@ -223,3 +223,46 @@ Problem 1-1: Comparison of running times | 2^n | | | | | | n! | | | | | ``` + +# Chapter 2 Getting Started + + +2.1 Insertion Sort + +Solves the sorting problem. + +Input: A sequence of `n` numbers `{a1,a2,...,aN}` +Output: A permutation (reordering) of the input sequence such that: + + `{a1 <= a2 <= ... <= aN}` + +The numbers that we want to sort are known as keys. + +e.g. + +```plaintext + +a. [5, 2, 4, 6, 1, 3] + x i +b. [2, 5, 4, 6, 1, 3] + x x i +c. [2, 4, 5, 6, 1, 3] + x x x i +d. [2, 4, 5, 6, 1, 3] + x x x x i +e. [1, 2, 4, 5, 6, 3] + x x x x x i +f. [1, 2, 3, 4, 5, 6] +``` + +```plaintext +A = {5,2,4,6,1,3} + +for j = 2 to A.length + key = A[j] + i = j - 1 + while i > 0 and A[i] > key + A[i+1] = A[i] + i = i - 1 + A[i+1] = key +``` -- cgit v1.2.3