A list of key-value pairs is stored using two arrays namely keysand values, wher
ID: 3618748 • Letter: A
Question
A list of key-value pairs is stored using two arrays namely keysand values, where keys[i] hold the ith key and values[i]hold the ith value. Thus reordering of elements in keysrequires reordering of respective elements in values. Assuming thata key is either 0 or 1, write a non-recursive Java method to sortthe list in non-decreasing order by comparing the keys atmost n times. And the total running time should not exceedO(n). Youralgorithm must sort the list in-place and you should not createadditional lists. Example of a result list sorted by keys is asfollows:
keys: 0 0 0 0 1 1 1 1
values: 21 7 4 8 76 100 32 15
public class KeyValueList {
private int keys[];
private int values[];
private intmanyItems;
publicKeyValueList(int maxSize) {
keys = newint[maxSize];
values = newint[maxSize];
manyItems=0;
}
// Don’timplement accessor and mutuator methods.
public void swap(int s, int d) {
int temp;
temp =keys[s]; keys[s] = keys[d]; keys[d] = temp;
temp = values[s];values[s]= values[d]; values[d]= temp;
}
// manyItems is the number of elements to besorted.
// Simply ignore the values in comparisons.
public void sort() {
}//sort
}//KeyValueList