CLSR Chap2

Question 1

What indexes are compared during a single cycle of insertion sort?

Answer 1

The comparison is between the index being sorted and all previous indexes until the studied index is no longer greater than the previous.

Question 2

In insertion sort, what determines whether a swap is performed or not?

Answer 2

In insertion sort, a swap is performed if the rightmost index checked is smaller than the leftmost index (assuming ascending order).

Question 3

From what indexes of the array does the insertion sort algorithm need to loop through, and why?

Answer 3

Insertion sort needs to loop through array j=2 to Array.length because we need to loop through all elements of the array and we cannot swap the first element to the left.

Question 4

What is the condition needed to loop through all previous iterations in code?

Answer 4

while i > 0 and A[i] > key …. then perform the swap

Question 5

In insertion sort, how can we perform the swapping of two values in code?

Answer 5

A[i+1] = A[i], where i = j-1 is each the previous index.

Question 6

What range of indexes of elements are in order while searching element at index j?

Answer 6

All indexes to the left of index j-1 are presumably in order already, or A[1…j-1].