CODEWITHSUNDEEP
arraysscalasorting
lserlohn
lserlohn

Reputation: 6206

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

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?

Upvotes: 1

Views: 3033

Answers (4)

bottaio
bottaio

Reputation: 5093

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)

Upvotes: 1

jwvh
jwvh

Reputation: 51271

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)

Upvotes: 2

Kevin Hoerr
Kevin Hoerr

Reputation: 2609

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.

Upvotes: 2

Brian
Brian

Reputation: 20285

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)

Upvotes: 7

Related Questions