Counting sort (Scala)

From LiteratePrograms

Other implementations: C | C# | Haskell | Java | Python, functional | Scala

Here is a simple Counting sort in Scala:

<<counting_sort>>=
  // scaladoc (javadoc like) documentation 
  /**
  * 
  * @param array : array to sort
  * @param end   : number of elements to sort
  * @param max   : upper bound for array values
  * @param min   : lower bound for array values
  */
  def cSort( array: Array[Int], end: Int, max: Int, min: Int): Unit = {
    // precondition
    assume( end <= array.length 
            && array.subArray(0, end).forall( x => (min <= x && x <= max))) ;
    if ( end < 2) {}  // nothing to sort
    else if (end == 2) {
      if (array( 0) > array(1)) {
        // swap values
        val temp = array(0) ;
        array(0) = array(1) ;
        array(1) = temp ;
      }
    }
    else  {
      val sortRange = max - min +1 
      val count = new Array[Int]( sortRange)  
      val scratch = new Array[Int]( end) 
      def normalized( i: Int) = array( i) - min 
      count_values_and_accumulate
      // now count(normValue) == topmost (if repeated values) of order( normValue)  
      // reposition array values in scratch
      // each value at count( normValue) position 
      // decrementing count( normValue) for next position of repeated values
      for (val i <- Iterator.range( 0, end)) {
        val normValue = normalized( i) ;
        scratch( count( normValue) -1) = array(i) ;
        count( normValue) = count( normValue) -1 ;
      }
      // copy scratch ordered values back into array
      for (val i <- Iterator.range( 0, end)) { 
        array(i) = scratch( i)
      }
    }
  }

Count normalized values and accumulate counters, so each accumulated counter will hold the topmost ordered position for the value it indexes.

<<count_values_and_accumulate>>=
// init counters 
for (val i <- Iterator.range( 0, sortRange)){
  count( i) = 0 ;
}
// count normalized array values
for (val i <- Iterator.range( 0, end)) {
  val normValue = normalized( i) ;
  count( normValue) = count( normValue) +1 ;
}
// accumulate counters
for (val i <- Iterator.range( 1, sortRange)) {
  count( i) = count( i) + count( i -1)
}
/** 
* count(normValue) will hold the number of elements 
* with normalized value less than or equal to normValue, 
* so the topmost (for repeated values) order position
*
* {count(normValue) == 'count elements x where (normalized( x) <= normValue')} 
*/ 

Test module

<<CountingSortTest.scala>>=
package test;
import scala.testing.UnitTest ;
object CountingSortTest extends Application {
  counting_sort
  def test = {
    val sample1 = Array( 5, 3, 7, 10, 2, 7, 3)
    val expected1 = Array( 2, 3, 3, 5, 7, 7, 10)
    val min = List.fromArray( sample1) reduceLeft { (x: Int, y: Int) => Math.min( x,y)} ;
    val max = List.fromArray( sample1) reduceLeft { (x: Int, y: Int) => Math.max( x,y)} ;
    val actual1 = { 
                    cSort( sample1, sample1.length, max, min) ;
                    sample1 
                   }
    UnitTest.assertSameElements(  actual1, expected1)
  }
  test
}

Testing

scala test.CountingSortTest
passed ok

Download code