Exercise 2.3
Exercise 2.3-1¶
Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A = [3, 41, 52, 26, 38, 57, 9, 49].
Exercise 2.3-2¶
Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.
Pseudocode
MERGE(A, p, q, r)
1 n1 = q - p + 1 2 n2 = r - q 3 let L[1..n1+1] and R[1..n2+1] be new arrays 4 for i = 1 to n1 5 L[i] = A[p+i-1] 6 for j = 1 to n2 7 R[j] = A[q+j] 10 i = 1 11 j = 1 12 k = p 13 while i != n1 + 1 and j != n2 + 1 14 if L[i] <= R[j] 15 A[k] = L[i] 16 i = i + 1 17 else 18 A[k] = R[j] 19 j = j + 1 20 k = k + 1 21 if i = n1 + 1 22 for s = j to n2 23 A[k] = R[s] 24 k = k + 1 25 if j = n2 + 1 26 for s = i to n1 27 A[k] = L[s] 28 k = k + 1
Python code
def merge(A, p, q, r): """Merges sorted subarrays This procedure assumes that the subarrays A[p..q] and A[q+1..r] are sorted. Merges the subarrays to form single sorted subarray A[p..r] Args: A: Array to be sorted p: Index of start of first subarray q: Index of end of first subarray r: Index of end of second subarray """ n1 = q - p + 1 # length of subarray A[p..q] n2 = r - q # length of subarray A[q+1..r] # Initialize arrays L and R L = [A[p + i] for i in range(0, n1)] R = [A[q + j + 1] for j in range(0, n2)] # Construct A[p..r] from L and R in sorted order i, j, k = 0, 0, p while i != n1 and j != n2: if L[i] <= R[j]: A[k] = L[i] i += 1 else: A[k] = R[j] j += 1 k += 1 if i == n1: for s in range(j, n2): A[k] = R[s] k += 1 if j == n2: for s in range(i, n1): A[k] = L[s] k += 1 return A
def merge_sort(A): """Sorts the array `A` in ascending order using `Merge sort` algorithm Args: A: Array of numbers to be sorted Returns: Array of numbers in sorted, ascending order """ # Recursively callable method def merge_sort_r(A, p, r): if p < r: q = (p + r) // 2 merge_sort_r(A, p , q) # Sort first half merge_sort_r(A, q + 1, r) # Sort second half merge(A, p, q, r) # Merge first and second half merge_sort_r(A, 0, len(A) - 1) return A
tests = [ [31, 41, 59, 26, 41, 58], [], [40, 20], [1], [10, 9, 8, 7], [7, 8, 9, 10] ] for input_array in tests: print(f'Input: {input_array}') output_array = merge_sort(input_array) print(f'Sorted: {output_array}\n')
Input: [31, 41, 59, 26, 41, 58] Sorted: [26, 31, 41, 41, 58, 59] Input: [] Sorted: [] Input: [40, 20] Sorted: [20, 40] Input: [1] Sorted: [1] Input: [10, 9, 8, 7] Sorted: [7, 8, 9, 10] Input: [7, 8, 9, 10] Sorted: [7, 8, 9, 10]
Exercise 2.3-3¶
Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence:
T(n) = \left\{ \begin{array}{l} 2 & \text{if } n=2\\ 2T(n/2)+n & \text{if } n = 2^k, \text{ for } k > 1 \end{array} \right.is T(n) = n \text{ lg } n
Proof by mathematical induction
For, n = 2
Hence, the equation is true for n = 2 (base case)
Also, if n = 2^k, assume it is true for k.
For k+1,
Substituting for T(2^k),
Hence, by Mathametical Induction, the equation is true for all n = 2^k, \text{ for } k > 1
Exercise 2.3-4¶
We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1..n-1]. Write a recurrence for the running time of this recursive version of insertion sort.
To sort array A[1..n-1], it takes \Theta(n) time. Hence,
which gives, $$ T(n) = \Theta(n^2) $$
Python code (recursive)
def insertion_sort(A): """Sorts the array `A` in ascending order using `Insertion sort` algorithm, recursively Args: A: Array of numbers to be sorted Returns: Array of numbers in sorted, ascending order """ def rec(A, n): if n == 2 and A[0] > A[1]: A[0], A[1] = A[1], A[0] elif n > 2: # (i) Sort A[1 .. n - 1] recursively rec(A, n - 1) # (ii) Insert A[n] into sorted array A[1 .. n - 1] key = A[n - 1] # nth element i = n - 2 while i > -1 and A[i] > key: A[i+1] = A[i] i = i - 1 A[i + 1] = key rec(A, len(A)) return A
tests = [ [31, 41, 59, 26, 41, 58], [], [40, 20], [1], [10, 9, 8, 7], [7, 8, 9, 10] ] for input_array in tests: print(f'Input: {input_array}') output_array = insertion_sort(input_array) print(f'Sorted: {output_array}\n')
Input: [31, 41, 59, 26, 41, 58] Sorted: [26, 31, 41, 41, 58, 59] Input: [] Sorted: [] Input: [40, 20] Sorted: [20, 40] Input: [1] Sorted: [1] Input: [10, 9, 8, 7] Sorted: [7, 8, 9, 10] Input: [7, 8, 9, 10] Sorted: [7, 8, 9, 10]
Exercise 2.3-5¶
Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is \Theta(n\cdot log_2(n))
Pseudo code (Iterative)
BINARY-SEARCH(A, v)
1 low = 1, high = A.length 2 while low <= high 3 mid = (low + high) / 2 4 if A[mid] = v 5 return mid 6 else if A[mid] > v 7 high = mid - 1 8 else 9 low = mid + 1 10 return NIL
Python code (Iterative)
def binary_search(A, element): """Performs search for `element` in A using binary search algorithm Args: A: Input array element: Target element to be found in A Returns: Index of the element, if found, -1 otherwise """ low, high = 0, len(A) - 1 while low <= high: mid = (low + high) // 2 if A[mid] == element: return mid elif A[mid] > element: high = mid - 1 else: low = mid + 1 return -1
tests = [ {"A": [1, 4, 5, 6, 9], "v": 1, "index": 0}, {"A": [1, 4, 5, 6, 9], "v": 9, "index": 4}, {"A": [1, 4, 5, 6, 9], "v": 4, "index": 1}, {"A": [1, 4, 5, 6, 9], "v": 6, "index": 3}, {"A": [1, 4, 5, 6, 9], "v": 3, "index": -1}, ] for test in tests: A, v, index = test["A"], test["v"], test["index"] res = binary_search(A, v) print(f'A = {A}') print(f'v = {v}') print(f'Expected index = {index}') print(f'Actual index = {res}\n')
A = [1, 4, 5, 6, 9] v = 1 Expected index = 0 Actual index = 0 A = [1, 4, 5, 6, 9] v = 9 Expected index = 4 Actual index = 4 A = [1, 4, 5, 6, 9] v = 4 Expected index = 1 Actual index = 1 A = [1, 4, 5, 6, 9] v = 6 Expected index = 3 Actual index = 3 A = [1, 4, 5, 6, 9] v = 3 Expected index = -1 Actual index = -1
Pseudo code (Recursive)
BINARY-SEARCH(A, v, low, high)
1 if low > high 2 return NIL 3 mid = (low + high) / 2 4 if A[mid] = v 5 return mid 6 else if A[mid] > v 7 BINARY-SEARCH(A, v, low, mid - 1) 8 else 9 BINARY-SEARCH(A, v, mid + 1, high)
BINARY-SEARCH(A, v, 1, A.length)
Python code (Recursive)
def binary_search(A, element): """Performs search for `element` in A using binary search algorithm Args: A: Input array element: Target element to be found in A Returns: Index of the element, if found, -1 otherwise """ def search(low, high): if low > high: return -1 mid = (low + high) // 2 if A[mid] == element: return mid elif A[mid] > element: return search(low, mid - 1) else: return search(mid + 1, high) return search(0, len(A) - 1)
tests = [ {"A": [1, 4, 5, 6, 9], "v": 1, "index": 0}, {"A": [1, 4, 5, 6, 9], "v": 9, "index": 4}, {"A": [1, 4, 5, 6, 9], "v": 4, "index": 1}, {"A": [1, 4, 5, 6, 9], "v": 6, "index": 3}, {"A": [1, 4, 5, 6, 9], "v": 3, "index": -1}, ] for test in tests: A, v, index = test["A"], test["v"], test["index"] res = binary_search(A, v) print(f'A = {A}') print(f'v = {v}') print(f'Expected index = {index}') print(f'Actual index = {res}\n')
A = [1, 4, 5, 6, 9] v = 1 Expected index = 0 Actual index = 0 A = [1, 4, 5, 6, 9] v = 9 Expected index = 4 Actual index = 4 A = [1, 4, 5, 6, 9] v = 4 Expected index = 1 Actual index = 1 A = [1, 4, 5, 6, 9] v = 6 Expected index = 3 Actual index = 3 A = [1, 4, 5, 6, 9] v = 3 Expected index = -1 Actual index = -1
In worst case, v can be the first or last element. Search range becomes half at each iteration if v is not the middle element of the current range.
Hence,
which gives,
Exercise 2.3-6¶
Observe that the while loop of lines 5–7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1 .. j - 1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to \Theta(n\cdot log_2{n})?
Line 5-7 are as follows,
5 while i > 0 and A[i] > key 6 A[i+1] = A[i] 7 i = i - 1
Using binary search will not improve the worst-case running time to \Theta(n\cdot log_2{n}). Binary search will only indicate the proper position to insert. Whereas, lines 5-7 of procedure INSERTION-SORT shifts the elements which are larger than A[j]. Shifting the elements takes \Theta(j) time.
Exercise 2.3-7¶
Describe a \Theta(n\cdot log_2n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
We can use Merge Sort to sort the set S, which takes \Theta(n\cdot log_2n) time. Use sorted array S' to search from both the ends to find out if two elements exist whose sum is x, in \Theta(n) time.
Hence, overall running time is,
Pseudocode
SEARCH-FOR-PAIRS-OF-SUM(S, x)
1 Sort array S using Merge Sort 2 i = 1, j = S.length 3 while i < j 4 if S[i] + S[j] = x 5 return true 6 else if S[i] + S[j] < x 7 i = i + 1 8 else 9 j = j - 1 10 return false
Python code
def search_pairs_of_sum(S, x): """Determines whether or not there exists 2 elements in S with sum x Args: S: Input array x: sum value Returns: True if 2 elements are found in S with sum=x, False otherwise """ S = sorted(S) # Use built-in sort method for simplicity i, j = 0, len(S) - 1 while i < j: pair_sum = S[i] + S[j] if pair_sum == x: return True elif pair_sum < x: i += 1 else: j -= 1 return False
tests = [ {"S": [4, 9, 1, 2, 7, 6], "x": 10, "sum_exists": True}, {"S": [4, 9, 1, 2, 7, 6], "x": 3, "sum_exists": True}, {"S": [4, 9, 1, 2, 7, 6], "x": 12, "sum_exists": False} ] for test in tests: S, x, sum_exists = test["S"], test["x"], test["sum_exists"] res = search_pairs_of_sum(S, x) print(f'S = {S}') print(f'x = {x}') print(f'Expected: {sum_exists}') print(f'Actual : {res}\n')
S = [4, 9, 1, 2, 7, 6] x = 10 Expected: True Actual : True S = [4, 9, 1, 2, 7, 6] x = 3 Expected: True Actual : True S = [4, 9, 1, 2, 7, 6] x = 12 Expected: False Actual : False