Part 1: Give a pseudo-code (with explanations) for the most efficient algorithm, call it Rearrange1(A), that takes as input an array $A$ of $N$ positive integers and outputs another array $B$ in which even integers from $A$ appear before odd integers. Your algorithm should not use any other data structures except for standard arrays such as int[] in Java. For example, on input $A=\{12,8,9,4,19,16,41\}$ the algorithm can output $B=\{12$, $8,4,16,9,19,41 } .$ Note that even and odd integers do not need to appear in the same order as in A. For example, $B=\ {8,4,12,16,19,41,9\}$ is also a legitimate output. Explain the time complexity of your Rearrangel algorithm. How many passes over the arrays does it perform? How much additional space is created? Part 2: Give a pseudo-code (with explanations) for an improved and most efficient version of this algorithm, call it Rearrange2(A), which rearranges the input array A in-place, that is taking only a constant amount of additional space. In particular, your algorithm may not create any additional arrays. Explain the time complexity of your Rearrange2 algorithm. How many passes over the array A does it perform? How much additional space is created? CS.VS. 1085