Counting sort (Scala)

From LiteratePrograms

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')} 
*/

[edit]

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
}