How to sort an Array[Array[Int]] supposing inner array have the same size but we don't know it

Question

Let's consider the following Array[Array[Int]

val array = Array(Array(7,3,2,1), Array(3,2,5,1), Array(2,1,4,6), Array(1,2,3,4))

I would like to have this result

val sortedArray = Array(Array(1,2,3,4), Array(1,2,3,5), Array(1,2,3,7), Array(1,2,4,6))

If we know that each inner array have the same size n we start to sort each inner array then use sortBy

val sortedArray = array.map(_.sorted).sortBy(x => (x(0), x(1), x(2), x(3)))

Unfortunately if we don't know the inner array size in advance or if it's huge we cannot proceed as seen above. Maybe it is possible to define a custom ordering in a dynamic way..

In this case i can also do

val sortedArray = array.map(_.sorted).map(a => (a.reduce(_+_), a)).sortBy(_._1).map(_._2)

But it works because elements in each array are present a uniq time for each array.

Doesn't doing only array.map(_.sorted) get you the results you want ? — Anahcolus
– Anahcolus, Commented May 14, 2017 at 8:47
No because i want to sort the result of array.map(_sorted) to have them ordered — KyBe
– KyBe, Commented May 14, 2017 at 8:50
@KyBe In your desired sortedArray result, shouldn't Array(1,2,3,7) come before Array(1,2,4,6)? — Jeffrey Chung
– Jeffrey Chung, Commented May 14, 2017 at 12:02

PH88 · Accepted Answer · 2017-05-15 01:00:40Z

3

You can implement your own Ordering for the array elements like:

val array = Array(Array(7,3,2,1), Array(3,2,5,1), Array(2,1,4,6), Array(1,2,3,4))

implicit object IntArrayOrdering extends Ordering[Array[Int]] {
  override def compare(x: Array[Int], y: Array[Int]): Int =
    compareStream(x.toStream, y.toStream)

  private def compareStream(x: Stream[Int], y: Stream[Int]): Int = {
    (x.headOption, y.headOption) match {
      case (Some(xh), Some(yh))  => 
        if (xh == yh) {
          compareStream(x.tail, y.tail)
        } else {
          xh.compare(yh)
        }
      case (Some(_), None) => 1
      case (None, Some(_)) => -1
      case (None, None) => 0
    }
  }
}

array.map(_.sorted).sorted

edited May 15, 2017 at 1:00

answered May 14, 2017 at 9:08

PH88

1,81613 silver badges12 bronze badges

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

2 Comments

Alexey Romanov Over a year ago

But note that this particular implementation is going to perform badly, as tail on arrays has to create a new array and copy elements there, unlike Lists.

PH88 Over a year ago

True. A simple way to improve performance, as I did in the updated answer above, is to turn Array[Int] into Stream[Int] before the recursion. Of course, you might squeeze even more speed by going lower level and access the Array[Int] directly by index.

Collectives™ on Stack Overflow

How to sort an Array[Array[Int]] supposing inner array have the same size but we don't know it

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related