0

The problem I'm facing is sorting a List of Double values in Scala also containing some kind of placeholder values (Double.NaN in the example below. However, these can be set as required for the sorting to work.), which should keep their position after sorting.

Input:

val placeholder = Double.NaN
List(placeholder, 5.0, 2.0, placeholder, 4.0, 3.0, placeholder)

Output:

List(placeholder, 2.0, 3.0, placeholder, 4.0, 5.0, placeholder)

How can I sort Double values in a list without altering the position of placeholder values? I'm searching for a solution to work with Scala 2, specifically 2.12

Thanks for your help!

Niklas2501
  • 25
  • 4
  • this is a bit tricky with doubles as you should not compare floating point numbers by equality, so you would have to define some precision which you'll use to compare. – Pavel Jan 08 '23 at 11:47
  • 1
    if you want to implement your own sorting algorithm you can check this topic as well https://stackoverflow.com/questions/17138854/sorting-array-while-skipping-value – Pavel Jan 08 '23 at 14:19
  • 1
    @Pavel While you should not compare floating numbers by equality in general, for sorting you usually want to do it, because comparison used for sorting needs to be transitive, which comparison with epsilon (aka tolerant comparison or fuzzy comparison) is not. See also https://stackoverflow.com/questions/47018744/effects-of-violating-compareto-transitivity-contract-due-to-numerical-precision – Suma Jan 09 '23 at 08:52

3 Answers3

4

One way is to sort the list and insert back the placeholders at right position.

This is not optimal, optimisation left to the reader as an exercise, but here's the idea:

val placeholder = Double.NaN
val list = List(placeholder, 5.0, 2.0, placeholder, 4.0, 3.0, placeholder)

val sorted = list.filterNot(_.isNaN).sorted

def insertSorted(in: List[Double], sorted: List[Double]): List[Double] = {
  in match {
    case Nil => Nil
    case head :: tail => 
      if (head.isNaN)
        placeholder :: insertSorted(tail, sorted)
      else
        sorted.head :: insertSorted(tail, sorted.tail)
  }
}

insertSorted(list, sorted)
// List(NaN, 2.0, 3.0, NaN, 4.0, 5.0, NaN)

This only works with NaN as placeholder. If using another value (like -1), regular comparison should be used.

Also, as raised in the comments, comparison on doubles can lead to surprises, use with caution.

Gaël J
  • 11,274
  • 4
  • 17
  • 32
2

This solution could also be written as a fold:

  def sort(list: List[Double]): List[Double] = {
    val (sorted, _) = list
      .foldLeft((List.empty[Double], list.sorted)) { case ((result, sortedInput), n) =>
        if (n.isNaN) (result :+ placeholder, sortedInput)
        else (result :+ sortedInput.head, sortedInput.tail)
      }
    sorted
  }

Again not optimal, but possibly the most straightforward if performance is not a high priority.

Chris C
  • 229
  • 2
  • 3
0

foldRight is stack safety

def sort(in: List[Double]): List[Double] = {
    val sortedIn = in.filterNot(_.isNaN).sorted.reverse
    val (result, _) = in.foldRight((List.empty[Double], sortedIn)) {
        case (n, (result, list)) =>
            if (n.isNaN) (placeholder :: result, list)
            else (list.head :: result, list.tail)
    }
    result
}
CHEg
  • 1