Ruby: insert and sort numbers

Question

I have to create a method in Ruby which inserts a number and sorts the resulting list.

Input would be like:

insert_number([2.0,3.5,4.8], 4.1) 

which should output:

[2.0,3.5,4.1,4.8]

With input like:

insert_number([], 5.1) 

it should output:

[5.1]

Here is my incomplete code:

def insert_number(list, number)
  new_list = []               
  position = 0                         
  number_has_been_inserted = false     # Remember whether a new number 
  # has been inserted.
  while position < list.length 
    position += 1
    new_list = list + [number] 
    ...
  end
  ...
    new_list
end

print insert_number([2.0,3.5,4.8], 4.1)

Answer 1

bsearch only works if the original input array is already sorted, which is not a pre-condition. – @pjs

Considering your original array is sorted you can use binary search here. It will perform much better because it won't need to perform expensive sorting procedure on each insert.

This one mutates original array

def insert_number(arr, num)
  i = (0...arr.size).bsearch{ |a| arr[a] > num }
  i ||= arr.size
  arr.insert(i, num)
end

arr = []
insert_number(arr, 1)
#=> [1]
insert_number(arr, 2)
# => [1, 2]
insert_number(arr, 2.1)
# => [1, 2, 2.1]
insert_number(arr, 1.3)
#=> [1, 1.3, 2, 2.1]

And this one will return new array on each call

def insert_number(arr, num)
  i = (0...arr.size).bsearch{ |a| arr[a] > num }
  i ||= arr.size
  arr[0, i] + [num] + arr[i..-1]
  # or
  # arr.dup.insert(i, num)
end

arr = []
arr = insert_number(arr, 1)
#=> [1]
arr = insert_number(arr, 2)
# => [1, 2]
arr = insert_number(arr, 2.1)
# => [1, 2, 2.1]
arr = insert_number(arr, 1.3)
#=> [1, 1.3, 2, 2.1]

PS:

Recent Ruby versions have bsearch_index – @Stefan

Answer 2

I'd do something like:

def insert_number(list, number)
  (list << number).sort
end

list = [1, 2, 3]
insert_number(list, 2.1) # => [1, 2, 2.1, 3]
insert_number(list, 4.1) # => [1, 2, 2.1, 3, 4.1]
insert_number([], 1) # => [1]

The problem is this changes list. If that's not desired then use dup:

def insert_number(list, number)
  (list.dup << number).sort
end

list = [1, 2, 3]
insert_number(list, 2.1) # => [1, 2, 2.1, 3]
insert_number(list, 4.1) # => [1, 2, 3, 4.1]
insert_number([], 1) # => [1]

or a "splat" AKA *:

def insert_number(list, number)
  [*list, number].sort
end

list = [1, 2, 3]
insert_number(list, 2.1) # => [1, 2, 2.1, 3]
insert_number(list, 4.1) # => [1, 2, 3, 4.1]
insert_number([], 1) # => [1]

[*list, number] tells Ruby to explode the array list into its elements, effectively creating a new array:

[1, 2, 3, number]