counting sort


See On Github

Data

Source Code


class CountingSort {

  def countSort(listToBeSorted: List[Int], minValue: Int, maxValue: Int): List[Int] =

    listToBeSorted.foldLeft(Array.fill(maxValue - minValue + 1)(0)) { (arr, n) =>
      arr(n - minValue) += 1
      arr
    }.zipWithIndex.foldLeft(List[Int]()) {
      case (lst, (cnt, ndx)) => List.fill(cnt)(ndx + minValue) ::: lst
    }.reverse
}

import org.scalatest.{Matchers, FunSuite}

class CountingSortTest extends FunSuite with Matchers {

  test("generateCountList should generate") {
    val objectForCountingSort = new CountingSort

    objectForCountingSort.countSort(List(11,1,22,33,23),1,33) should be(List(1,11,22,23,33))
    objectForCountingSort.countSort(List(1,2,3,4,5,6,7,8,9),1,9) should be(List(1,2,3,4,5,6,7,8,9))
  }
}