Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
数え上げソート。バケツソート。スリープソート。
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 + " ")
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment