Java Inserting numbers into an array in order

Question

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.

Yo compare each element with element you are about to insert and find appropriate index and then insert. — Yoshikage Kira
– Yoshikage Kira, Commented Sep 28, 2019 at 20:05
Possible duplicate of Inserting an element into an array in sorted order — Yoshikage Kira
– Yoshikage Kira, Commented Sep 28, 2019 at 20:08
You should start with a pen and paper and think about how would you perform the task of inserting a number into a specific position of a given list. When you have the theoretical stuff done, then you can start about the implementation — Tom
– Tom, Commented Sep 28, 2019 at 20:08
The given code is problematic in several ways, but a "high-level" pointer that is relevant here is codereview.stackexchange.com/questions/36221/… — Marco13
– Marco13, Commented Sep 28, 2019 at 23:55

Bohemian · Accepted Answer · 2019-09-28 20:40:14Z

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).

Kaplan · Accepted Answer · 2019-10-02 01:25:23Z

1

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

edited Oct 2, 2019 at 1:25

answered Sep 28, 2019 at 21:15

Kaplan

3,94621 silver badges22 bronze badges

Comments

TacoIntrusion · Accepted Answer · 2019-10-01 02:19:28Z

0

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

answered Oct 1, 2019 at 2:19

TacoIntrusion

313 bronze badges

Collectives™ on Stack Overflow

Java Inserting numbers into an array in order

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related