Best way to insert an element into an ordered array in Scala

Question

I have an Array, or Seq looks like

val myArray = collection.mutable.ArrayBuffer[Int](1,4,8,10,12,13)

val newElem = 7

I want to insert the new element into the Array at the right position, so that the array is still ordered.

I don't want to generate a new array here.

My solution is to find the insert position first, and then insert it.

def findInsertPosition(myArray: collection.multable.ArrayBuffer[Int], newElem: Int): Int

then call

myArray.insert(pos, newElem)

The question is how to write the findInsertPosition function in Scala style, without using while, for loops?

or if you have better solution?

Brian · Accepted Answer · 2018-01-18 20:24:43Z

7

Find the insert position with lastIndexWhere and add one to it then insert at that position.

scala> val xs = scala.collection.mutable.ArrayBuffer(1,4,8,10,12,13)
xs: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 4, 8, 10, 12, 13)

scala> xs.insert(xs.lastIndexWhere(_ < 7) + 1, 7)

scala> xs
res10: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 4, 7, 8, 10, 12, 13)

answered Jan 18, 2018 at 20:24

Brian

20.3k6 gold badges36 silver badges55 bronze badges

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

2 Comments

lserlohn Over a year ago

Thanks. Followup question: how to implement it if no lastIndexWhere function?

Brian Over a year ago

There may be other methods you could use from the standard library to accomplish the same thing. See the answers others have provided for examples. If you don't want to use a while loop and write something from scratch, I'd try a recursive function that takes newElem and myArray and returns an index you use to insert.

Kevin Hoerr · Accepted Answer · 2018-01-18 20:30:53Z

2

This might be a bit inefficient, but it works:

def findInsertPosition(myArray: collection.mutable.ArrayBuffer[Int], newElem: Int): Int =
  myArray.takeWhile(_ < newElem).size

It will be the correct index when inserting.

answered Jan 18, 2018 at 20:30

Kevin Hoerr

2,6491 gold badge13 silver badges21 bronze badges

Comments

jwvh · Accepted Answer · 2018-01-18 21:17:32Z

2

Find the correct index point and insert.

val idx = myArray.indexWhere(_>newElem)
myArray.insert(if (idx<0) myArray.length else idx, newElem)
// ArrayBuffer(1, 4, 7, 8, 10, 12, 13)

edited Jan 18, 2018 at 21:17

answered Jan 18, 2018 at 21:11

jwvh

51.3k7 gold badges42 silver badges70 bronze badges

Comments

bottaio · Accepted Answer · 2018-01-18 21:28:23Z

1

The first thing that comes to my mind:

myArray.insert(
  Stream.range(0, myArray.length)
    .find(a(_) >= newElem)
    .getOrElse(myArray.length), 
  newElem)

another approach would be something similar to Brian's answer

myArray.insert(
  myArray.indexWhere(_ >= newElem),
  newElem)

edited Jan 18, 2018 at 21:28

answered Jan 18, 2018 at 20:44

bottaio

5,1133 gold badges21 silver badges49 bronze badges

Collectives™ on Stack Overflow

Best way to insert an element into an ordered array in Scala

4 Answers 4

2 Comments

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Related