How to order a list of tuples of integers in Scala

Question

Given a list of tuples of integers:

List[(Int, Int, Int)] =  List((2,1,3), (4,2,6),...)

I'd like to sort them by their third component but if two tuples have the same third component then I'd like to order them by their second component. For instance, I'd like (6,3,9) < (4,7,9). Here is what I tried:

     def order(k: List[(Int, Int, Int)]) = {
        var t = List[Int]()
        if (k.map(_._3) == t) {
            k.sortBy(_._2)
            t = k.map(_._3)
            k
        } else {
            k.sortBy(_._3)
            t = k.map(_._3)
            k
        }   
     }

Thank you in advance!

Answer 1

A rather simple and surprisingly fast approach is to use a stable sorting algorithm, and sort first by the first component, then by the second, then by the third. Since you sorted last by the third component, this will be dominant. When using a stable sort, objects tied in the last component will be ordered by the previous one:

Sorting.stableSort(k, (x, y) => x._1 < y._1)
Sorting.stableSort(k, (x, y) => x._2 < y._2)
Sorting.stableSort(k, (x, y) => x._3 < y._3)

or equivalently (but probably more expensive, as it builds a sequence of keys):

Sorting.stableSort(k, x => x._1)
Sorting.stableSort(k, x => x._2)
Sorting.stableSort(k, x => x._3)

(assuming that Seq.sortBy is not stable.)

Alternatively (and this is the more classic and obvious approach), write a comparator (Ordering) that uses the third component if different, then the second if different and finally the first one. This is probably not very "scalish", but it is IMHO very clean and understandable:

val result = intOrdering.compare(x._3, y._3)
if (result == 0) result = intOrdering.compare(x._2, y._2)
if (result == 0) result = intOrdering.compare(x._1, y._1)
result

again, you can also use a key function (but this will need 2x as much memory):

k.sortBy(x => (x._3, x._2, x._1))

Answer 2

It seems that

k.sortBy(x => (x._3 , x._2))

does the job and returns

List[(Int, Int, Int)] = List((2,1,3), (4,2,6), (6,3,9), (4,7,9), (6,7,11),
          (8,4,12), (10,5,15), (12,1,17), (12,6,18), (8,14,18), (6,17,19))

which also works for (12,6,18), (8,14,18)