. A list ofkey-value pairs is stored using two arrays namely keys and values,whe
ID: 3618749 • Letter: #
Question
. A list ofkey-value pairs is stored using two arrays namely keys and values,where keys[i] hold the ith key and values[i] hold theith value. Thus reordering of elements in keys requiresreordering of respective elements in values. Assuming that a key iseither 0 or 1, write a non-recursive Java method to sort the listin non-decreasing order by comparing the keys at most ntimes. 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
Explanation / Answer
// manyItems is the number of elements to besorted. // Simply ignore thevalues in comparisons. publicvoid sort() { int i = 0; int j =keys.length-1; while(true) { while(keys[i] == 0 && i=0) { j--; } if(i >= j) { break; } else { swap(i, j); } } }//sortRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.