数え上げソート。バケツソート。スリープソート。

on_sort.scala

object Main {
  def main(args: Array[String]) {
    val l = Seq(3,1,5,3,2)
    val range = l.max + 1
    println(countingSort(l, range))
    println(bucketSort(l, range))
    sleepSort(l)
  }

  // 数え上げソート
  // 箱を要素の最大値分作り、リストの値をいれる。同じものを数えるため++する。
  // 
  // 3 1 5 3 2   リスト
  // 0 0 0 0 0 0 maxの5+1の箱を作る
  // 0 1 1 2 0 1 数えて添字のとこにいれる
  // 1 2 3 3 5   1が1つ。2が1つ。3が2つ。5が1つ。
  def countingSort(l: Seq[Int], range: Int): Seq[Int] = {
    val r = Array.fill[Int](range)(0)

    l.foreach { n =>
      r.update(n, r(n) + 1)
    }
    r.zipWithIndex.flatMap {
      case (n, i) => if (n > 0) Seq.fill(n)(i) else Nil
    }
  }

  // バケツソート
  // 最大値分箱を作るのではなく、hash(n/3)を使い、箱を減らして効率化。
  // 
  // 3 1 5 3 2
  // [1,2] [3,5,3]
  // [1,2] [3,3,5]
  // 1 2 3 3 5
  def bucketSort(l: Seq[Int], range: Int): Seq[Int] = {
    def h(n: Int): Int = n / 3
    val r = Array.fill[Seq[Int]](h(range))(Nil)

    l.foreach { n =>
      r.update(h(n), n +: r(h(n)))
    }
    r.flatMap { _.sorted }
  }

  // スリープソート
  // 箱ではなく時間を使う。
  // 
  // 3 1 5 3 2
  // 3秒待ってecho 1秒待ってecho ...
  // 1 2 3 3 5
  def sleepSort(l: Seq[Int]): Unit = {
    import scala.collection.parallel.ForkJoinTaskSupport
    import scala.concurrent.forkjoin.ForkJoinPool

    // 要素の分だけスレッドを作りsleepしてechoする。これはひどい。
    val lp = l.par
    lp.tasksupport = new ForkJoinTaskSupport(new ForkJoinPool(l.size))
    lp.foreach { n =>
      Thread.sleep(n)
      print(n + " ")
    }
  }
}