a) Implement the fastest possible algorithm to insert a new entry into a sorted
ID: 3564675 • Letter: A
Question
a) Implement the fastest possible algorithm to insert a new entry into a sorted (in ascending order) array of strings. Duplicates are NOT allowed - throw an IllegalArgumentException if a duplicate is attempted to be inserted. After insertion, the array should still be in sorted order. You will get at most half the credit if your algorithm is not the fastest possible. (Fastest here refers to the real clock time, not big O, for large values of n).
// Inserts a string into a sorted array A, containing n entries, where n is // strictly less than the length of the array. (There are more spaces in the // array than entries.) Throws an IllegalArgumentException if string already exists // (case insensitive match). // After the insertion, the array is still sorted.
public static void sortedInsert(String[] A, int n, String item) {
Explanation / Answer
public static void sortedInsert(String[] A, int n, String item) {
String []B = new String[n+1];
int i;
for(i=0; i<n; i++){
if(item.compareTo(A[i] < 0){
B[i] = A[i];
}
else{
break;
}
}
for(j=i; j<n; j++){
B[j] = A[j];
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.