Open lpatmo opened 5 years ago
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
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.