Ruby insert object into existing sorted array of objects

Question

I have the following existing array of Dog objects, which is ordered by the age attribute:

class Dog
  attr_accessor :age

  def initialize(age)
    @age = age
  end
end

dogs = [Dog.new(1), Dog.new(4), Dog.new(10)]

I want to now insert a new dog record and have it go in the proper place in the array.

Let's say I want to insert this object:

another_dog = Dog.new(8)

I want to insert it into the array and let it be the third item in the array.

This is a contrived example meant to demonstrate how I specifically want to insert an item into an existing ordered array. I realize I could just create a brand new array and sort all the objects all over again, but that is not what I am aiming to do here.

Thanks!

Answer 1

One idiomatic way to do this is to just append and then sort in place. Arrays are mutable in Ruby:

dogs.push(Dog.new(7)).sort_by!(&:age)

Depending on your use case, you may want to consider an alternative data structure that offers better performance, such as a binary tree. You may also want to implement Comparable, in which case you can simplify to Array#sort!.

Answer 2

In Ruby 2.3+, there's an Array#bsearch_index you can use to determine the index you need to pass to Array#insert:

dogs = [Dog.new(1), Dog.new(4), Dog.new(10)]

another_dog = Dog.new(8)
insert_at = dogs.bsearch_index { |dog| dog.age >= another_dog.age }
dogs.insert(insert_at, another_dog)
puts dogs.inspect
# => [Dog.new(1), Dog.new(4), Dog.new(8), Dog.new(10)]

This only works if the Array is already sorted (standard, when using binary search for anything), but it sounds like that's the case.

If you're using Ruby < 2.3, you don't have bsearch_index, but insert is still available, you can throw together a quick search for the index on your own and then use insert.