Created
January 19, 2014 09:49
-
-
Save ryoppy/8502599 to your computer and use it in GitHub Desktop.
数え上げソート。バケツソート。スリープソート。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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