[Java]

Here is the code that needs to be implemented

import java.io.*; import java.util.*; public class Lab2 { /** * 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 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 ton 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. a