Adding an integer to a sorted ArrayList at the correct index

Question

Say I have a sorted list (in ascending order) like thisArrayList<Integer> arr = Arrays.asList(1, 2, 3, 5, 6). There will be no duplicates in the list.

I want to add an integer to it at the correct index so that the array is still sorted after I add the element, like so: arr.add(4) // now arr = {1, 2, 3, 4, 5, 6}.

How do I achieve this elegantly WITHOUT resorting to sorting AFTER I add the element by using Collections.sort(arr) or something.

I'm looking for a better/more elegant solution than the one I currently have (I don't even know if it works for all cases lol):

int n = 4 // number I want to add to the list
boolean added = false;

for(int i < 0; i < arr.size(); i++) {
   if(n < arr.get(i)) {
     arr.add(i, n)
     added = true;
     break;
   }
}

if(added == false) {
  arr.add(n)
}

Thanks for the help in advance!

@RobbyCornelissen Sorry, I forgot to mention. No duplicates in the list. — Hat
– Hat, Commented May 12, 2020 at 3:51

John Kugelman · Accepted Answer · 2020-05-12 04:17:15Z

7

The linear search you're doing now is O(n), plus O(n) for the call to add().

You can find the insertion point in O(log n) time with Collections.binarySearch(), then call add() just like you're doing now. The overall complexity will still be O(n) since O(log n + n) = O(n), but it'll be slightly faster and the code'll be a good bit shorter.

int i = Collections.binarySearch(arr, n);

// `n` not found. Retrieve the insertion point from the return value.
if (i < 0) {
    i = -i - 1;
}

arr.add(i, n);

edited May 12, 2020 at 4:17

answered May 12, 2020 at 4:11

John Kugelman

364k70 gold badges555 silver badges600 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Anonymous Over a year ago

In my most honest opinion the advantage of this answer is not so much that it is more efficient (which it is for very large lists), but rather that the code is more elegant and concise.

Jagat · Accepted Answer · 2020-05-12 04:09:53Z

0

Use a TreeSet as an intermediary. A TreeSet is a binary search tree, and when you iterate through it, you get the elements in sorted order.

Set<String> set = new TreeSet<Integer>(arr);
set.add(n);
arr = new ArrayList<Integer>(set);

answered May 12, 2020 at 4:09

Jagat

1,4022 gold badges16 silver badges25 bronze badges

Comments

RaffleBuffle · Accepted Answer · 2020-05-12 04:34:40Z

You'd use binary search to determine the insert position.

Either wrap the built in Collections.binarySearch method:

// insert v into list if not present, maintaining order
// return whether list was updated
static boolean insert(List<Integer> list, int v)
{
    int pos = Collections.binarySearch(list, v);
    if(pos >= 0)
        return false;

    pos = -pos - 1;
    list.add(pos, v);
    return true;
}

Or just for interest, roll your own:

static boolean insert(List<Integer> list, int v)
{
    int low = 0; 
    int high = list.size();
    while(low < high)
    {
        int mid = low + (high-low)/2;
        if(list.get(mid) < v)
            low = mid+1;
        else if(list.get(mid) > v)
            high = mid;
        else
            return false;               
    }
    list.add(low, v);
    return true;
}

Collectives™ on Stack Overflow

Adding an integer to a sorted ArrayList at the correct index

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related