Using Java to implement the data structure and insert/serach operations. There a
ID: 3912757 • Letter: U
Question
Using Java to implement the data structure and insert/serach operations.
There are two arrays: one array is longer than the other, and both arrays are kept sorted. The length of the shorter array is the square root of the length of the longer array even though it may have empty entries if it is not yet full.
To add an element, you use insertion sort to insert the element into the shorter array. If the short
array fills up, re-allocate the shorter and longer arrays and merge the two old arrays into the
new longer array. The new short array is empty. Then, to search an element, use binary search on
both the long and the short arrays. This data structure has O(lg n) searching time complexity and O(square root of n) time complexity for adding an element.
Explanation / Answer
import java.util.Scanner;
class arr
{
void main()
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the length of shorter array");
int n1=sc.nextInt();
System.out.println(n1);
int n2=n1*n1;
int a1[];
int a2[];
a1=new int[n1];
a2=new int[n2];
int i,j,k;
int flag[]=new int[n1];
System.out.println("Entering elements in shorter array ");
for(i=0;i<n1;i++)
{
System.out.println("press 1 to enter an element to the array , 0 to skip this element");
flag[i]=sc.nextInt();
if(flag[i]==1)
{
System.out.println("Enter the element");
a1[i]=sc.nextInt();
}
}
System.out.println("Entering elements in longer array");
for(i=0;i<n2;i++)
{
System.out.println("Enter the element");
a2[i]=sc.nextInt();
}
insertionSort(a1,n1);
insertionSort(a2,n2);
printArray(a1,n1);
printArray(a2,n2);
fillArray(a1,n1,flag);
printArray(a1,n1);
printArray(a2,n2);
int m=n1+n2;
int b[]=new int[m];
for(i=0;i<n1;i++)
{ b[i]=a1[i];
}
for(i=n1,j=0;i<m;i++,j++)
{ b[i]=a2[j];
}
insertionSort(b,m);
for(int p=1;p>0;p++)
{ System.out.println("Merged the two arrays into the longer array and emptied the shorter array");
n2=m;
double d=Math.sqrt(n2);
n1=(int) d;
a1=new int[n1];
a2=new int[n2];
flag=new int[n1];
for(i=0;i<n2;i++)
{ a2[i]=b[i];
}
fillArray(a1,n1,flag);
printArray(a1,n1);
printArray(a2,n2);
m=n1+n2;
b=new int[m];
for(i=0;i<n1;i++)
{ b[i]=a1[i];
}
for(i=n1,j=0;i<m;i++,j++)
{ b[i]=a2[j];
}
insertionSort(b,m);
System.out.println("Enter 0 to exit program , 1 to continue");
int z=sc.nextInt();
if(z==0)
break;
}
}
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, k, j;
for (i = 1; i < n; i++)
{
k = arr[i];
j = i-1;
while (j >= 0 && arr[j] > k)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = k;
}
}
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println(" ");
}
// filling shorter array
void fillArray(int a1[], int n1, int flag[])
{ int i,j,k;
Scanner sc=new Scanner(System.in);
printArray(a1,n1);
System.out.println("Filling the shorter array");
for(i=0;i<n1;i++)
{ System.out.println(a1[i]);
if(flag[i]==0)
{ System.out.println("Enter an element");
a1[i]=sc.nextInt();
}
}
insertionSort(a1,n1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.