Scala: How to sort an array within a specified range of indices?

Question

And I have a comparison function "compr" already in the code to compare two values.

I want something like this:

Sorting.stableSort(arr[i,j] , compr)

where arr[i,j] is a range of element in array.

Answer 1

Take the slice as a view, sort and copy it back (or take a slice as a working buffer).

scala> val vs = Array(3,2,8,5,4,9,1,10,6,7)
vs: Array[Int] = Array(3, 2, 8, 5, 4, 9, 1, 10, 6, 7)

scala> vs.view(2,5).toSeq.sorted.copyToArray(vs,2)

scala> vs
res31: Array[Int] = Array(3, 2, 4, 5, 8, 9, 1, 10, 6, 7)

Outside the REPL, the extra .toSeq isn't needed:

vs.view(2,5).sorted.copyToArray(vs,2)

Answer 2

Split array into three parts, sort middle part and then concat them, not the most efficient way, but this is FP who cares about performance =)

val sorted = 
  for {
    first       <- l.take(FROM)
    sortingPart <- l.slice(FROM, UNTIL)
    lastPart    <- l.takeRight(UNTIL)
  } yield (first ++ Sorter.sort(sortingPart) ++ lastPart)

Answer 3

Something like that:

def stableSort[T](x: Seq[T], i: Int, j: Int, comp: (T,T) => Boolean ):Seq[T] = {
    x.take(i) ++ x.slice(i,j).sortWith(comp) ++ x.drop(i+j-1)
}                                         

def comp: (Int,Int) => Boolean = { case (x1,x2) => x1 < x2 } 
val x = Array(1,9,5,6,3)                           
stableSort(x,1,4, comp)
// > res0: Seq[Int] = ArrayBuffer(1, 5, 6, 9, 3)

If your class implements Ordering it would be less cumbersome.

Answer 4

This should be as good as you can get without reimplementing the sort. Creates just one extra array with the size of the slice to be sorted.

def stableSort[K:reflect.ClassTag](xs:Array[K], from:Int, to:Int, comp:(K,K) => Boolean) : Unit = {
  val tmp = xs.slice(from,to)
  scala.util.Sorting.stableSort(tmp, comp)
  tmp.copyToArray(xs, from)
}