These are the instructions from my professor and I have no idea what to do at al

Question

These are the instructions from my professor and I have no idea what to do at all. I have attached MyArraySorted (the code that is written is what we have done in class so far and the instructions below is what we need to add and that is what I am unsure about).

1. Create another class 'MyArraySorted' (I have attached it to this post). 'MyArraySorted' keeps the array sorted at all times. For example, when you add numbers 4, 1, 3 in this order, MyArraySorted will have them in ascending order, i.e. 1, 3, 4. Note that add(int val) needs to find the right place to add the given value and shift some numbers to the right to keep all numbers sorted. It is also true for constructor with array input. In other words, one of the constructors, MyArraySorted(int[] numbers) will copy numbers from 'numbers' but those numbers need to be in ascending order at the end of the constructor. Do NOT use function sort() anywhere. Write an application 'MyArraySortedDemo.java to test it.

package apps;

public class MyArraySorted {
int[] nums;
int numElements=0;

public MyArraySorted(){
  nums = new int[100];
}
public MyArraySorted(int size){
  nums = new int[size];
}
public MyArraySorted(int[] numbers){
  nums = new int[numbers.length];
  for(int i=0; i<numbers.length;i++)
   nums[i] = numbers[i];
  numElements = nums.length;
}
public void printArray() {
  for(int i=0; i<numElements ; i++)
   System.out.print(nums[i]+" ");
  System.out.println();
}
public void remove(int val) {
  int index = linearSearch(val);
  if (index >= 0) { // if val is found
   
//   for(int i=index;i<numElements-1;i++)
//    nums[i] = nums[i+1];
   nums[index] = nums[numElements-1];
   numElements--;
  }
}
public void add(int val) {
  if (numElements < nums.length)// if nums is not full
   nums[numElements++] = val;
  else { // nums is full
   int[] new_nums = new int[nums.length*2];
   for(int i=0;i<nums.length;i++)
    new_nums[i] = nums[i];
   new_nums[nums.length] = val;
   nums = new_nums;
   numElements++;
  }
}

public int findMaxIdx() {
  int maxIdx = 0;
  for(int i=1; i<nums.length; i++)
   if(nums[i] > nums[maxIdx]) // new challenger is greater
    maxIdx = i;
  return maxIdx;
}
private int binarySearch(int val) {
  int start = 0;
  int end = nums.length-1;
  int midpoint;
  while(start<=end) {
   midpoint = (start + end)/2;
   if (val > nums[midpoint])
    start = midpoint + 1;
   else if (val < nums[midpoint])
    end = midpoint - 1;
   else // val == nums[midpoint]
    return midpoint;
  }
  return -1;
}

public int search(int val) {
  return binarySearch(val);
}
private int linearSearch(int val){
  // returns the index of the given value 'val'.
  // if 'val' is not found, returns -1
  for(int i=0;i<nums.length;i++)
   if (nums[i] == val)
    return i;
  
  return -1;
}
private void generateNumbers() {
  // nums[0]=0, nums[1]=2, nums[2]=4,...
  for(int i=0; i<nums.length; i++)
   nums[i] = 2*i;
}

}

Explanation / Answer

MyArraySorted.java

package apps;

public class MyArraySorted {

int[] nums;
int numElements = 0;

public MyArraySorted() {
nums = new int[100];
}

public MyArraySorted(int size) {
nums = new int[size];
}

/**
* Constructor to create an array with initial values. This method finds the
* exact location to insert an element and then inserts it
*
* @param numbers array to be inserted
*/
public MyArraySorted(int[] numbers) {
nums = new int[numbers.length];
for (int i = 0; i < numbers.length; i++) {
insert(numbers[i]);
}

}

/**
* Prints the details of array like Total elements,Max array capacity and
* the array itself
*/
public void printArray() {
System.out.println("Total elements:" + numElements);
System.out.println("Max array capacity:" + nums.length);
System.out.print("Array:");
for (int i = 0; i < numElements; i++) {
System.out.print(nums[i] + " ");
}
System.out.println();
}

/**
* Removes the first occurence of an element from array if present
*
* @param val number to be removed
*/
public void remove(int val) {
int index = linearSearch(val);//gets teh location of the element

if (index >= 0) { //if present
int i = index;
while (i < (numElements - 1)) {
nums[i] = nums[i + 1];//shifts all elements towards its right to left
i++;
}
numElements--;
} else//index -1 means not present
{
System.out.println("Number not found");
}
}

/**
* Add an element to array at correct location
*
* @param val number to insert
*/
public void add(int val) {
if (numElements < nums.length)// if array is not full
{
insert(val);
} else { // array is full
int[] new_nums = new int[nums.length * 2];//expand the size of array
for (int i = 0; i < nums.length; i++) {
new_nums[i] = nums[i];//copy elements
}
nums = new_nums;
insert(val);
}
}

/**
* @return max element in the array
*/
public int findMaxIdx() {
return nums[numElements - 1];
}

/**
* Performs binary search and returns the position of an element
*
* @param val number to search
* @return -1 if not present ,else location of number
*/
private int binarySearch(int val) {
int start = 0;
int end = nums.length - 1;
int midpoint;
while (start <= end) {
midpoint = (start + end) / 2;
if (val > nums[midpoint]) {
start = midpoint + 1;
} else if (val < nums[midpoint]) {
end = midpoint - 1;
} else // val == nums[midpoint]
{
return midpoint;
}
}
return -1;
}

public int search(int val) {
return binarySearch(val);
}

/**
* Performs linear search and returns the position of an element
*
* @param val number to search
* @return -1 if not present ,else location of number
*/
private int linearSearch(int val) {
// returns the index of the given value 'val'.
// if 'val' is not found, returns -1
for (int i = 0; i < nums.length; i++) {
if (nums[i] == val) {
return i;
}
}

return -1;
}

private void generateNumbers() {
// nums[0]=0, nums[1]=2, nums[2]=4,...
for (int i = 0; i < nums.length; i++) {
nums[i] = 2 * i;
}
}

/**
* inserts a new number to array which will be sorted after insertion
*
* @param number number to insert
*/
private void insert(int number) {
int i = 0;
if (numElements == 0) {
nums[i] = number;
numElements++;
return;
}
while (i < numElements && nums[i] < number) {
i++;
}

int j = numElements - 1;
while (j >= i) {
nums[j + 1] = nums[j];
j--;
}
nums[i] = number;
numElements++;

}

}

MyArraySortedDemo.java

package apps;

import java.util.Scanner;

public class MyArraySortedDemo {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
  
System.out.println("Testing array created using default constructor...");
MyArraySorted arr1=new MyArraySorted();//instance uses default constructor   
arr1.printArray();
  
System.out.println(" Testing array created by supplying size...");
System.out.print("Enter size of array to create:");
int size=in.nextInt();
MyArraySorted arr2=new MyArraySorted(size);//instance created by supplying size   
arr2.printArray();
  
System.out.println(" Testing array created by passing initial elements as array {23,56,45,12,10}..");
int a[]={23,56,45,12,10};
MyArraySorted arr3=new MyArraySorted(a);//instance created by supplying an array
arr3.printArray();
  
int element;
System.out.println(" Testing addition of an element...");
System.out.print("Enter number to insert to array:");
element=in.nextInt();
arr3.add(element);
arr3.printArray();
System.out.print("Enter number to insert to array:");
element=in.nextInt();
arr3.add(element);
arr3.printArray();
System.out.print("Enter number to insert to array:");
element=in.nextInt();
arr3.add(element);
arr3.printArray();
  
  
  
System.out.println(" Testing removal of an element(first occurence)...");
System.out.print("Enter number to remove from array:");
element=in.nextInt();
arr3.remove(element);
arr3.printArray();
System.out.print("Enter number to remove from array:");
element=in.nextInt();
arr3.remove(element);
arr3.printArray();
System.out.print("Enter number to remove from array:");
element=in.nextInt();
arr3.remove(element);
arr3.printArray();
  
System.out.println(" Testing max element...");
arr3.printArray();
System.out.println("Max element:"+arr3.findMaxIdx());
  
  
  
  
}
  
}

Sample Output

run:
Testing array created using default constructor...
Total elements:0
Max array capacity:100
Array:

Testing array created by supplying size...
Enter size of array to create:4
Total elements:0
Max array capacity:4
Array:

Testing array created by passing initial elements as array {23,56,45,12,10}..
Total elements:5
Max array capacity:5
Array:10 12 23 45 56

Testing addition of an element...
Enter number to insert to array:3478
Total elements:6
Max array capacity:10
Array:10 12 23 45 56 3478
Enter number to insert to array:12
Total elements:7
Max array capacity:10
Array:10 12 12 23 45 56 3478
Enter number to insert to array:46
Total elements:8
Max array capacity:10
Array:10 12 12 23 45 46 56 3478

Testing removal of an element(first occurence)...
Enter number to remove from array:23
Total elements:7
Max array capacity:10
Array:10 12 12 45 46 56 3478
Enter number to remove from array:56
Total elements:6
Max array capacity:10
Array:10 12 12 45 46 3478
Enter number to remove from array:1323
Number not found
Total elements:6
Max array capacity:10
Array:10 12 12 45 46 3478

Testing max element...
Total elements:6
Max array capacity:10
Array:10 12 12 45 46 3478
Max element:3478
BUILD SUCCESSFUL (total time: 20 seconds)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.