# 2.1 Insertion sort

## 2.1-1

Using Figure 2.2 as a model, illustrate the operation of $\text{INSERTION-SORT}$ on the array $A = \langle 31, 41, 59, 26, 41, 58 \rangle$.

\begin{aligned} A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 26, 31, 41, 59, 41, 58 \rangle \\ A & = \langle 26, 31, 41, 41, 59, 58 \rangle \\ A & = \langle 26, 31, 41, 41, 58, 59 \rangle \end{aligned}

## 2.1-2

Rewrite the $\text{INSERTION-SORT}$ procedure to sort into nonincreasing instead of nondecreasing order.

 1 2 3 4 5 6 7 8 INSERTION-SORT(A) 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 

## 2.1-3

Consider the searching problem:

Input: A sequence of $n$ numbers $A = \langle a_1, a_2, \ldots, a_n \rangle$ and a value $v$.

Output: An index $i$ such that $v = A[i]$ or the special value $\text{NIL}$ if $v$ does not appear in $A$.

Write pseudocode for linear search, which scans through the sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

 1 2 3 4 5 LINEAR-SEARCH(A, v) for i = 1 to A.length if A[i] == v return i return NIL 

Loop invariant: At the start of each iteration of the for loop, the subarray $A[1..i - 1]$ consists of elements that are different than $v$.

Initialization: Initially the subarray is the empty array, so the prove is trivial.

Maintenance: On each step, we know that $A[1..i - 1]$ does not contain $v$. We compare it with $A[i]$. If they are the same, we return $i$, which is a correct result. Otherwise, we continue to the next step. We have already insured that $A[1..i - 1]$ does not contain $v$ and that $A[i]$ is different from $v$, so this step preserves the invariant.

Termination: The loop terminates when $i > A.length$. Since $i$ increases by $1$ and $i > A.length$, we know that all the elements in $A$ have been checked and it has been found that $v$ is not among them. Thus, we return $\text{NIL}$.

## 2.1-4

Consider the problem of adding two $n$-bit binary integers, stored in two $n$-element arrays $A$ and $B$. The sum of the two integers should be stored in binary form in an $(n + 1)$-element array $C$. State the problem formally and write pseudocode for adding the two integers.

Input: An array of booleans $A = \langle a_1, a_2, \ldots, a_n \rangle$ and an array of booleans $B = \langle b_1, b_2, \ldots, b_n \rangle$, each representing an integer stored in binary format (each digit is a number, either $0$ or $1$, least-significant digit first) and each of length $n$.

Output: An array $C = \langle c_1, c_2, \ldots, c_{n + 1} \rangle$ such that $C' = A' + B'$ where $A'$, $B'$ and $C'$ are the integers, represented by $A$, $B$ and $C$.

 1 2 3 4 5 6 7 8 ADD-BINARY(A, B) C = new integer[A.length + 1] carry = 0 for i = 1 to A.length C[i] = (A[i] + B[i] + carry) % 2 // remainder carry = (A[i] + B[i] + carry) / 2 // quotient C[i] = carry return C