4. Suppose that you are given an array A[0..n-1] of numbers, and an index i 0...

Transcribed Image Text:

4. Suppose that you are given an array A[0..n-1] of numbers, and an index "i" 0<=i<n-1. The index "i" implicitly divides the array into two parts A[0..i] and A[i..n-1]. Design an in-place algorithm swap that swaps these two subarrays without changing the order of the elements. As an example, assume you are given the following numbers: A = [10, 2, 4, 8, 9, 3, 15, 6] and index "i" = 2. Then after the swap operation, the array would turn into: A = [8, 9, 3, 15, 6, 10, 2, 4]. void swap (vector<int> &A, int i) You must write a recursive auxiliary function to solve this problem, i.e., swapAux(A, 0, i, n-1); The following figure illustrates the 3 recursive cases you will encounter: leftSize == rightSize 9 3 15 6 10 2 4 8 1024893 15 6 10 2 10 2 4 8 8 9 3 15 6 3 15 6 leftSize rightSize 8 9 3 10 2 15 6 leftSize > rightSize 10 23 15 6 4 8 9 a. When leftSize== rightSize, we simply do pairwise swaps, and we are done. b. If the leftSize < rightSize, then we swap the first 2* leftSize elements as shown. We are now left with n-leftSize elements to process. c. If leftSize > rightSize, then we swap the last rightSize elements as shown. We are now left with m- rightSize elements to process. Implement this recursive function in C++. Since this is a tail-recursive function, you can turn it into an iterative algorithm. Also try implementing iterative algorithm. 4. Suppose that you are given an array A[0..n-1] of numbers, and an index "i" 0<=i<n-1. The index "i" implicitly divides the array into two parts A[0..i] and A[i..n-1]. Design an in-place algorithm swap that swaps these two subarrays without changing the order of the elements. As an example, assume you are given the following numbers: A = [10, 2, 4, 8, 9, 3, 15, 6] and index "i" = 2. Then after the swap operation, the array would turn into: A = [8, 9, 3, 15, 6, 10, 2, 4]. void swap(vector<int> &A, int i) You must write a recursive auxiliary function to solve this problem, i.e., swapAux(A, 0, i, n-1); The following figure illustrates the 3 recursive cases you will encounter: leftSize == rightSize 9 3 15 6 10 2 4 8 1024893 15 6 10 2 10 2 4 8 8 9 3 15 6 3 15 6 leftSize rightSize 8 9 3 10 2 15 6 leftSize » rightSize 10 23 15 6 4 8 9 a. When leftSize == rightSize, we simply do pairwise swaps, and we are done. b. If the leftSize< rightSize, then we swap the first 2*leftSize elements as shown. We are now left with n-leftSize elements to process. c. If leftSize > rightSize, then we swap the last rightSize elements as shown. We are now left with m- rightSize elements to process. Implement this recursive function in C++. Since this is a tail-recursive function, you can turn it into an iterative algorithm. Also try implementing iterative algorithm. 4. Suppose that you are given an array A[0..n-1] of numbers, and an index "i" 0<=i<n-1. The index "i" implicitly divides the array into two parts A[0..i] and A[i..n-1]. Design an in-place algorithm swap that swaps these two subarrays without changing the order of the elements. As an example, assume you are given the following numbers: A = [10, 2, 4, 8, 9, 3, 15, 6] and index "i" = 2. Then after the swap operation, the array would turn into: A = [8, 9, 3, 15, 6, 10, 2, 4]. void swap (vector<int> &A, int i) You must write a recursive auxiliary function to solve this problem, i.e., swapAux(A, 0, i, n-1); The following figure illustrates the 3 recursive cases you will encounter: leftSize == rightSize 9 3 15 6 10 2 4 8 1024893 15 6 10 2 10 2 4 8 8 9 3 15 6 3 15 6 leftSize rightSize 8 9 3 10 2 15 6 leftSize > rightSize 10 23 15 6 4 8 9 a. When leftSize== rightSize, we simply do pairwise swaps, and we are done. b. If the leftSize < rightSize, then we swap the first 2* leftSize elements as shown. We are now left with n-leftSize elements to process. c. If leftSize > rightSize, then we swap the last rightSize elements as shown. We are now left with m- rightSize elements to process. Implement this recursive function in C++. Since this is a tail-recursive function, you can turn it into an iterative algorithm. Also try implementing iterative algorithm. 4. Suppose that you are given an array A[0..n-1] of numbers, and an index "i" 0<=i<n-1. The index "i" implicitly divides the array into two parts A[0..i] and A[i..n-1]. Design an in-place algorithm swap that swaps these two subarrays without changing the order of the elements. As an example, assume you are given the following numbers: A = [10, 2, 4, 8, 9, 3, 15, 6] and index "i" = 2. Then after the swap operation, the array would turn into: A = [8, 9, 3, 15, 6, 10, 2, 4]. void swap(vector<int> &A, int i) You must write a recursive auxiliary function to solve this problem, i.e., swapAux(A, 0, i, n-1); The following figure illustrates the 3 recursive cases you will encounter: leftSize == rightSize 9 3 15 6 10 2 4 8 1024893 15 6 10 2 10 2 4 8 8 9 3 15 6 3 15 6 leftSize rightSize 8 9 3 10 2 15 6 leftSize » rightSize 10 23 15 6 4 8 9 a. When leftSize == rightSize, we simply do pairwise swaps, and we are done. b. If the leftSize< rightSize, then we swap the first 2*leftSize elements as shown. We are now left with n-leftSize elements to process. c. If leftSize > rightSize, then we swap the last rightSize elements as shown. We are now left with m- rightSize elements to process. Implement this recursive function in C++. Since this is a tail-recursive function, you can turn it into an iterative algorithm. Also try implementing iterative algorithm.

Answer rating: 100% (QA)

The question provides an algorithmic challenge where one must swap two subarrays of a given array in C without altering the order of elements within t... View the full answer