Implement the fastest possible algorithm to insert a new entry into a sorted (in
ID: 3798442 • Letter: I
Question
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 sortedlnsert(String[] A, int n, String item) {Explanation / Answer
Please find the required program and output below: Please find the comments against each line for the description:
import java.util.Arrays;
class Test
{
public static void sortedInsert(String A[],int n,String item)throws Exception{
int l=0,mid,h=n,pos=-1; //initialize variables
while(l<h) //doing a binary search to find if the element is found, if not return the position to insert
{
mid=(l+h)/2; //find the mid
if(item.equals(A[mid])) //if the item to insert is present throw exception
{
pos = (mid+1);
throw new IllegalArgumentException("Duplicate item");
} else if(item.compareTo(A[mid])<0) {
h=mid-1;
} else if(item.compareTo(A[mid])>0)
{
l=mid+1;
}
}
pos = pos == -1 ? l : pos ;
for(int i=n-1; i>pos; i--){ //replacing all the values in position in array after item to insert
A[i] = A[i-1];
}
if(pos == n)
pos--;
A[pos] = item; //insert the new item
}
public static void main(String[] args)
{
String A[] = {"a","b","c","e","f","g","h",""};
try{
sortedInsert(A,8,"d");
}catch(Exception e){
e.printStackTrace();
System.out.println(e.getMessage());
}
System.out.println("Array: "+Arrays.toString(A));
}
}
---------------------------------------------------------
OUTPUT:
Array: [a, b, c, d, e, f, g, h]