[Java]

The code that needs to be implemented

import java.io.*; import java.util.*; public class Lab2 { /** * Problem 1: Arrange the given array such that all even numbers are in increasing * order at even indices and all odd numbers are in decreasing order at odd indices. */ private static void problem1(int[] arr) { // Implement me! } /** * Problem 2: Determines for each entry its position in the sorted array. */ private static int[] problem2(int[] arr) { // Implement me! return new int[] { }; } // --------------------------------------------------------------------- // Do not change any of the code below! static class IntKVPair implements Comparable { public int key; public int value; public IntKVPair(int key, int value) { this.key = key; this.value = value; } public int compareTo(IntKVPair other) { return this.key - other.key; } } private static final int LabNo = 2; private static final Random rng = new Random(654321); private static boolean testProblem1(int[][] testCase) { int[] arr = testCase[0]; int[] answer = arr.clone(); problem1(answer); if (answer == null) return false; if (answer.length != arr.length) return false;

for (int i = 2; i answer[i - 2]) return false; } Arrays.sort(arr); Arrays.sort(answer); for (int i = 0; i

for (int i = 1; i

{ int rndInd = rng.nextInt(size - i) + i; int tmp = numbers[i]; numbers[i] = numbers[rndInd]; numbers[rndInd] = tmp; } return new int[][] { numbers }; } private static int[][] createProblem2(int lineNo) { int maxSize = Math.min(lineNo, 500); int size = rng.nextInt(maxSize) + 2; int[] numbers = getUniqueRandomNumbers(size); Arrays.sort(numbers); int[] solution = new int[size]; for (int i = 0; i

int[] integers = new int[maxSize]; for (int i = 0; i Problem 1 You are given an unsorted array A of non-negative integers. It contains the same number of even and of odd numbers. Implement an algorithm such that all odd numbers in A are at odd indices and all even numbers are at even indices. Additionally, even numbers should be sorted in increasing order and odd numbers should be sorted in decreasing order. Your algorithm should run in O(n log n) time. Problem 2 You are given an array A with n distinct elements. Implement an O(n log n)-time algorithm that creates an array B where all elements are in range from 0 to n - 1 and where the order of elements is the same as in A. That is, 0 has the same index in B as the smallest element in A, 1 has the same index in B as the second smallest element in A, and so on. For example, if A = [4, 9, 1,5), then B = [1,3,0,2). Hint: Use key-value pairs where the key is the original element in A and the value is its index in A. The given file contains a class IntKVPair. It represents a key-value pair of integers and an IntkVPair-array can be sorted by their keys