Getting Started

What does the insertion sort algorithm solve?
The insertion sort algorithm solves the sorting problem.

What are the numbers to be sorted also called?
The numbers to be sorted are also called the keys.

What is the data associated with the keys called?
The data associated with the keys is called the satellite data.

What is the combination of a key and satellite data called?
The combination of a key and satellite data is called a record.

When describing a sorting algorithm, we focus on the ..., but it is important to remember that there usually is associated ... ...
When describing a sorting algorithm, we focus on the keys, but it is important to remember that there usually is associated satellite data.

How would you sort a deck of cards using insertion sort?
You would sort a desk of cards using insertion sort by taking cards from the deck with your right hand and placing them in their correct positions in your left hand.

What is the pseudocode for insertion sort?
The pseudocode for insertion sort is:

INSERTION-SORT(A,n)
	for i = 2 to n
		key = A[i]
		// Insert A[i] into the sorted subarray A[1:i-1]
		j = i - 1
		while j > 0 and A[j] > key
			A[j+1] = A[j]
			j = j - 1
		A[j+1] = key

Loop invariants and the correctness of insertion sort

...

Info

Loop Invariant Condition With Examples by GeeksforGeeks

A loop invariant proof is a form of mathematical ...
A loop invariant proof is a form of mathematical induction.

What does the proof of the base case correspond to in a loop invariant?
In a loop invariant, the proof of the base case corresponds to the invariant holding true before the first iteration.

What does the proof of the inductive step correspond to in a loop invariant?
In a loop invariant, the proof of the inductive step corresponds to the invariant holding true from iteration to iteration.

Todo

This section explains the loop invariant for the insertion sort algorithm.

Pseudocode conventions

Todo

This section explains the syntax of the pseudocode used throughout the book.

Question

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on an array initially containing the sequence .
...

Consider the procedure SUM-ARRAY on the facing page. It computes the sum of the numbers in array . State a loop invariant for this procedure, and use its initialization, maintenance, and termination properties fo show that the SUM-ARRAY procedure returns the sum of the numbers in .
...

Rewrite the INSERTION-SORT procedure to sort into monotonically decreasing instead of monotonically increasing order.
...

Consider the searching problem:
Input: A sequence of numbers stored in array and a value .
Output: An index such that equals or the special value NIL if does not appear in .
Write pseudocode for linear search, which scans through the array from beginning to end, looking for . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
...

Consider the problem of adding two -bit binary integers and , stored in two -element arrays and , where each element is either 0 or 1, , and . The sum of the two integers should be stored in binary form in an -element array , where . Write a procedure ADD-BINARY-INTEGERS that takes as input arrays and , along with the length , and returns array holding the sum.
...

2.2 Analyzing algorithms

What does it mean to analyze an algorithm?
To analyze an algorithm means to predict the resources an algorithm requires.

What do you most often consider when analyzing an algorithm?
When analyzing an algorithm, you most often consider computational time.

What do you need before you can analyze an algorithm?
Before you can analyze an algorithm, you need a model of the technology that it runs on.

What is a random-access machine (RAM)?
A RAM is a model of computation where algorithms are implemented as computer programs running on a generic processor.

How are instructions in the random-access machine (RAM) model executed?
Instructions in the RAM model are executed one after another without concurrent operations.

What does the random-access machine (RAM) model assume about the time to execute an instruction or access data?
The RAM model assumes that the time to execute an instruction or access data is the same for each instruction and data access (constant).

...

Analysis of insertion sort

...