Keep ArrayList sorted after every add call by finding index to add Integer very quickly (1 million add calls needed)

Question

My teacher wants me to add an Integer item one at a time to a generic arraylist inside MySortedArray Class. I have to add 1_000_000 items. The custom add method he wants me to implement in MySortedArray, needs to add able to sort the arraylist after every addition. However, sorting it a million times after every add() call is too slow. What am I supposed to do? I need to be able to find the index in the ArrayList where I should add the Integer item very quickly. Would binary search work?

    @Test
    void testRandomInts() {
        MySortedArray<Integer> ints = new MySortedArray<>(10);
        
        for (int i = 0; i < 200; i++) {
            int num = (int)(Math.random() * 10 + 1);
            ints.add(num);
        }
        System.out.println("array is: " + ints.contents.toString());
        assertTrue(isSorted(ints));
    }

My teacher is forcing us to use an ArrayList :( MySortedArray Class does implement Comparable, so I'm not sure if I'm supposed to be using the compareTo method to find the index where I would add the item. But, I need to find the index really fast. — , Oct 04 '20 at 20:36
Your teacher is probably intending for you to use a binary search to figure out which index to insert the next element at. — Green Cloak Guy, Oct 04 '20 at 20:38
Does this answer your question? [How to sort an ArrayList in Java](https://stackoverflow.com/questions/18441846/how-to-sort-an-arraylist-in-java) — flaxel, Oct 04 '20 at 20:39
Cause I got this error before: The method binarySearch(List extends Comparable super T>>, T) in the type Collections is not applicable for the arguments (MySortedArray, T) — , Oct 04 '20 at 20:39
Why do you want to use the `MySortedArray`? If it is necessary for you, can you post this class? It is necessary that this class import the `Comparator` interface. — flaxel, Oct 04 '20 at 20:43
We aren't supposed to use Comparator for this lab. The class only extends Comparable. public class MySortedArray > implements GenericSortedArray { — , Oct 04 '20 at 20:46

score 0 · Accepted Answer · answered Oct 04 '20 at 20:58

0

  int index = Collections.binarySearch(contents, item);
  if (index < 0) index = ~index;
  contents.add(index, item);

answered Oct 04 '20 at 20:58

You can simplify your code a little bit with a [short-if-else](https://stackoverflow.com/questions/4461996/short-if-else-statement). – flaxel Oct 04 '20 at 21:02
2

Code-only answers are flagged as low-quality. Can you add a brief explanation of how this works and why it's a good solution to the problem? Thanks! – ggorlen Oct 04 '20 at 21:26

Keep ArrayList sorted after every add call by finding index to add Integer very quickly (1 million add calls needed)

1 Answers1