[Introduction to Algorithms] Problems 2.1 to 2.4: Insertion Sort

[lpatmo]

2.1

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array [31, 41, 59, 26, 41, 58]

2.2

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of non- decreasing order.

2.3

Consider the searching problem:

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

2.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 C 1/-element array C . State the problem formally and write pseudocode for adding the two integers.

[lpatmo]

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array [31, 41, 59, 26, 41, 58]

[31, 41, 59, 26, 41, 58] // examine 41
[31, 41, 59, 26, 41, 58] // examine 59
[31, 41, 59, 26, 41, 58] // examine 26
[31, 41, 26, 59,41, 58] //move 26
[31, 26, 41, 59, 41, 58]
[26, 31, 41, 59, 41, 58]
[26, 31, 41, 59, 41, 58] //examine 41
[26, 31, 41, 41, 59, 58] //move 41
[26, 31, 41, 41, 59, 58] //examine 58
[26, 31, 41, 41, 58, 59] //move 58

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

mark first element as sorted
for each unsorted element X
  'extract' the element X
  for j = lastSortedIndex down to 0
    if current element at the j position < X
      Move sorted element to the right by 1
    break loop and insert X here