CODEWITHSUNDEEP
javacomputer-science
TacoIntrusion
TacoIntrusion

Reputation: 31

Java Inserting numbers into an array in order

I am having problems with an assignment. I'm fairly new to coding and I am having a hard time trying to figure out how to do this. My professor supplied code for adding and removing items from an array but he wants us to add a method that would add items to the array in the correct position. This is the supplied code:

import java.util.*;

public class MyArrayList {
private Object[]buffer;
private int currentSize;

public MyArrayList(){
   final int INITIAL_SIZE=10;
  buffer = new Object[INITIAL_SIZE];
  currentSize=0;
  }

public int size() {
  return currentSize;
  }

private void checkBounds(int n){
  if (n<0||n>= currentSize){
     throw new IndexOutOfBoundsException();
     }
  }
public Object get (int pos){
  checkBounds(pos);
  return buffer[pos];
  }
public Object remove(int pos){
  checkBounds(pos);
  Object removed = buffer[pos];
  for (int i = pos+1; i < currentSize; i++){
     buffer[i-1] = buffer[i];
  }
  currentSize--;
  return removed;
}
public boolean add(int pos, Object newElement){
  growBufferIfNecessary();
  currentSize++;
  checkBounds(pos);
  for(int i = currentSize - 1; i > pos; i--){
     buffer[i] = buffer [i-1];
  }
  buffer[pos] = newElement;
  return true;
}
public boolean addLast(Object newElement){
  growBufferIfNecessary();
  currentSize++;
  buffer[currentSize -1] = newElement;
  return true;
}
 private void growBufferIfNecessary(){
  if (currentSize==buffer.length){
     Object[] newBuffer = new Object[2*buffer.length];
     for(int i=0; i<buffer.length; i++){
     newBuffer[i] = buffer[i];
     }
  buffer = newBuffer;
   }
} 

}

This is our assignment:

Add a method called "public void insert(int n)" that will add n to your MyArrayList object in the correct position maintaining the sorted order. Use your existing MyArrayList class with necessary modification.Here is a test case:

MyArrayList list = new MyArrayLst();

list.insert(5); insert(10); insert(8); insert(20); insert(6);

If you print the list now, it should print as:

5

6

8

10

20

So this is what I have so far in my main method:

 import java.util.*;

 public class ArrayListHomework {
 public static void main (String[]args){
 MyArrayList list = new MyArrayList();

 list.insert(5);
 list.insert(10);
 list.insert(8);
 list.insert(20);
 list.insert(6);
 for (int i=0; i<list.size(); i++){

     System.out.println(list.get(i));

   }
  }  
 }

I am super lost as to how to start this insert method. Any help would be appreciated. Thanks.

Upvotes: 3

Views: 757

Answers (3)

Kaplan
Kaplan

Reputation: 3758

not exactly like insertion sort, because there are free spaces with null-values

public void insert( int n ) {
  growBufferIfNecessary();
  for( int i = 0; i < buffer.length; i++ ) {
    if( buffer[i] == null ) {
      buffer[i] = n; currentSize++;
      break;
    }
    else if( buffer[i + 1] != null ) {
      int n1 = ((Number)buffer[i]).intValue();
      int n2 = ((Number)buffer[i + 1]).intValue();
      if( n1 < n && n2 > n ) {
        System.arraycopy( buffer, i + 1, buffer, i + 2, currentSize - i - 1 );  // line 1
        buffer[i + 1] = n; currentSize++;  // line 2
        break;
      }
    }
  }
}

the add() function could substitute  line 1  and  line 2

Upvotes: 1

TacoIntrusion
TacoIntrusion

Reputation: 31

Thank you everyone for your help and suggestions. I got it to work by using the code that Marco13 suggested: https://codereview.stackexchange.com/questions/36221/binary-search-for-inserting-in-array#answer-36239 Hope everyone has a great day and happy programming. -TJ

Upvotes: 0

Bohemian
Bohemian

Reputation: 425198

Sadly, and inexcusably, the code provided by your “professor” has a bug in the add() method, here:

public boolean add(int pos, Object newElement){
    growBufferIfNecessary();
    currentSize++;
    checkBounds(pos);
    // rest of method

Because checkBounds() is not called first, if pos is out of bounds, currentSize will be incremented (and the buffer unnecessarily grown), putting the instance in an inconsistent/erroneous state.

Coding 101: First, check parameters.

To fix:

public boolean add(int pos, Object newElement){
    checkBounds(pos);
    growBufferIfNecessary();
    currentSize++;
    // rest of method

To answer your question, you must implement what’s called an insertion sort. Briefly, this means use a loop to iterate over all elements, and insert the new element at the point you encounter a larger element, or reach the end of the elements.

Note that if your array elements are not already sorted, calling insert() is meaningless. To handle this case, you should consider throwing an IllegalStateException if elements are out of order (you can check as you iterate that the previous element is not greater than the current element as you iterate).

Upvotes: 3

Related Questions