Java Вставка чисел в массив по порядку

Question

У меня проблемы с заданием.Я довольно новичок в программировании, и мне трудно понять, как это сделать.Мой профессор предоставил код для добавления и удаления элементов из массива, но он хочет, чтобы мы добавили метод, который добавил бы элементы в массив в правильном положении.Это предоставленный код:

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;
   }
} 

}

Это наше назначение:

Добавьте метод с именем "public void insert (int n)", который добавит n к вашему объекту MyArrayList в правильномположение, поддерживающее отсортированный порядок.Используйте существующий класс MyArrayList с необходимой модификацией. Вот тестовый пример:

MyArrayList list = new MyArrayLst ();

list.insert (5);вставки (10);вставки (8);вставки (20);insert (6);

Если вы распечатываете список сейчас, он должен печататься как:

5

6

8

10

20

Итак, это то, что я пока имею в своем основном методе:

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

   }
  }  
 }

Я очень запутался в том, как запустить этот метод вставки.Любая помощь будет оценена.Спасибо.

Answer 1

К сожалению и непростительно, код, предоставленный вашим «профессором», содержит ошибку в методе add(), здесь:

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

Поскольку checkBounds() не вызывается первым, если posвыходит за пределы, currentSize будет увеличен (и буфер излишне увеличен), переведя экземпляр в противоречивое / ошибочное состояние.

Кодирование 101: Сначала проверьте параметры.

Исправление:

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

Чтобы ответить на ваш вопрос, вы должны реализовать так называемую сортировку вставок .Вкратце, это означает использование цикла для итерации по всем элементам и вставка нового элемента в тот момент, когда вы встретите более крупный элемент, или достижение конца элементов.

Обратите внимание, что если элементы массива еще не созданыотсортировано, звонить insert() бессмысленно.Чтобы справиться с этим случаем, вам следует подумать о выдаче IllegalStateException, если элементы не в порядке (вы можете проверить, что при повторении итерации предыдущий элемент не больше текущего элемента при выполнении итерации).

Answer 2

не совсем как сортировка вставкой, потому что есть свободные места с нулевыми значениями

public void insert( int n ) {
  growBufferIfNecessary();
  for( int i = 0; i < buffer.length; i++ ) {
    if( buffer[i] == null ) {
      buffer[i] = n;
      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, buffer.length - i - 2 );  // line 1
        buffer[i + 1] = n;  // line 2
        break;
      }
    }
  }
}

функция add() может заменить строку 1 и строку 2