package kapitel_07

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 7, Sortieren
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_07_07_CountingSort_App extends App {

  def CountingSort(a: Array[Int], l: Int, r: Int): Unit = {

    if (r - l <= 1) return

    var M = a.max
    val count: Array[Int] = Array.fill(M+1)(0)

    for (i <- l to r)
      count(a(i)) = count(a(i)) + 1

    var i = l
    for (j <- 1 to M)
      for (k <- 1 to count(j)) {
        a(i) = j
        i = i+1
      }
  }

  val a: Array[Int] = Array(6,8,9,2,3,10,7,5,1,4)
  CountingSort(a, 0, a.length-1)
  println(a.mkString(", "))

}