What are the fundamental operations of an unsorted array? Why is the insertion n
ID: 3745703 • Letter: W
Question
What are the fundamental operations of an unsorted array?
Why is the insertion not supported for unsorted array?
What is the time complexity of deleting an element from a sorted array? Does it have better time complexity than deleting a node from an unsorted array? Why?
Programming:
4.1 Download and study program P1-1.
Add a testing class that can test all the operations defined in the unsortedArrayAccess class.
Make your testing menu-driven.
4.2 Download and study program P1-2.
Add a testing class that can test all the operations defined in the sortedArrayAccess class. Make your testing menu-driven.
4.3 Modify program P1-2 so that the array is of Employee type. The sorting key is the employee’s id. The class Employee is given blow:
import java.util.Scanner;
public class employee
{
public int id;
public String name;
public double salary;
public void Input()
{
System.out.println("Enter name: ");
name = new Scanner(System.in).nextLine();
System.out.println("Enter ID: ");
id = Integer.parseInt(new Scanner(System.in).nextLine());
System.out.println("Enter Salary: ");
salary = Double.parseDouble(new Scanner(System.in).nextLine());
}
public void Output()
{
System.out.printf("Name: %1$s, ID: %2$s, Grade: %3$s ", name, id, salary);
}
public String toString()
{
return String.format("[Name: {0}, ID: {1}, Grade: {2}]", name, id, salary);
}
}
Add a testing class that can test all the operations defined in the sortedArrayAccess class.
Modify the sortedArrayAccess class by adding a method that find the employee who has the highest salary.
Modify the sortedArrayAccess class by adding a method that find the average salary of all employees.
Make your testing menu-driven.
Program P1-1:
package p5_unsortedArrayAccess;
import java.util.*;
public class unsortedArrayAccess
{
public static double[] arr;
private int arraySize;
public unsortedArrayAccess(int scale)
{
arr = new double[scale];
arraySize = 0;
}
public double get(int i)
{
return arr[i];
}
public int search(double Key)
{
int i = 0;
while ((arr[i] != Key) && (i < arraySize))
{
i = i + 1;
}
if (i < arraySize)
{
return i;
}
else
{
System.out.println("There is no such item!");
return -1;
}
}
public void append(double Item)
{
arr[arraySize] = Item;
arraySize = arraySize + 1;
}
public double remove()
{
if (arraySize == 0)
{
System.out.println("There is no item in the array!");
return -1;
}
double x = arr[arraySize - 1];
arraySize = arraySize - 1;
return x;
}
public void deletion(double Key)
{
int k = search(Key);
if (k != -1)
{
for (int i = k; i < arraySize; i++)
{
arr[i] = arr[i + 1];
}
arraySize = arraySize - 1;
};
}
public void display()
{
if (arraySize == 0)
{
System.out.println("Array is empty!");
}
else
{
for (int i = 0; i < arraySize; i++)
{
System.out.println(arr[i]);
}
};
System.out.println("array size is " + arraySize);
}
}
Program P1-2:
package p5_SortedArrayAccess;
import java.util.*;
public class sortedArrayAccess
{
public static double[] arr;
private int arraySize;
public sortedArrayAccess(int scale)
{
arr = new double[scale];
arraySize = 0;
}
public final double get(int i)
{
return arr[i];
}
public final int BinarySearch(double Key)
{
int k = 0;
int lower = 0;
int upper = arraySize - 1;
while (lower < upper)
{
k = (lower + upper + 1) / 2;
if (Key == arr[k])
{
break;
}
if (Key < arr[k])
{
upper = k - 1;
}
else
{
lower = k + 1;
}
}
if (lower == upper)
{
k = lower;
}
if (Key == arr[k])
{
return k;
}
else
{
System.out.println("The item cannot be found!");
return -1;
}
}
public final void insertion(double Key, double Item)
{
if (arraySize == 0)
{
arr[0] = Item;
}
/* find the position for interting the given item */
int position = 0;
while (Key > arr[position] && position < arraySize)
{
position++;
}
for (int i = arraySize; i > position; i--)
{
arr[i] = arr[i - 1];
}
arr[position] = Item;
arraySize = arraySize + 1;
}
public final void deletion(double Key)
{
/* find the given item */
int position = BinarySearch(Key);
if (position != -1)
{
for (int i = position; i < arraySize - 1; i++)
{
arr[i] = arr[i + 1];
}
arraySize = arraySize - 1;
};
}
public final void display()
{
if (arraySize != 0)
{
for (int i = 0; i < arraySize; i++)
{
System.out.println(arr[i]);
}
};
System.out.println("The number of items is " + arraySize);
}
}
Explanation / Answer
What are the fundamental operations of an unsorted array
The fundamental operations of unsorted array are :
1. Search operation - The search operation taks liner time as we traverse through the array starting from first element till we find the search key or reach end of array
What is the time complexity of deleting an element from a sorted array? Does it have better time complexity than deleting a node from an unsorted array? Why?
Time complexity for deleting an element from sorted array is linear - O(N). The time complexity for deleting node from unsorted aray is alsolinear O(N) , hence it does not have better time complexity tahn deleting node from unsorted array. The reason for this is that because after the position of element to be deleted is found, the elemnts to the right of element to be deleted are to be shifted by positionto the left. This shfting of element take linear 0(N) time in both sorted and unsorted arrays. Even though search time for element to be dleted in sorted array is less but the shifting tim is O(N) in both types of arrays.
2.Insert operation - Insert operation is faster as we don't have to care for the position where to insert the element.
3. Deletion operation. - First we have tosearch through the array for element to be deleted and after that shifyt the remaining elements (to the right of removed element) by 1 step to left. takes linear time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.