diff options
author | Hubert Plociniczak <hubert.plociniczak@epfl.ch> | 2011-11-02 14:34:35 +0000 |
---|---|---|
committer | Hubert Plociniczak <hubert.plociniczak@epfl.ch> | 2011-11-02 14:34:35 +0000 |
commit | b6778be91900b8161e705dc2598ef7af86842b0b (patch) | |
tree | d15e8ec18a37eec212f50f1ace27714d7e7d4d34 /test/pending/shootout/heapsort.scala | |
parent | ac6c76f26d884a94d0c9ff54f055d3f9ab750bac (diff) | |
download | scala-b6778be91900b8161e705dc2598ef7af86842b0b.tar.gz scala-b6778be91900b8161e705dc2598ef7af86842b0b.tar.bz2 scala-b6778be91900b8161e705dc2598ef7af86842b0b.zip |
Begone t1737...
Diffstat (limited to 'test/pending/shootout/heapsort.scala')
-rw-r--r-- | test/pending/shootout/heapsort.scala | 72 |
1 files changed, 72 insertions, 0 deletions
diff --git a/test/pending/shootout/heapsort.scala b/test/pending/shootout/heapsort.scala new file mode 100644 index 0000000000..59b1fe27cb --- /dev/null +++ b/test/pending/shootout/heapsort.scala @@ -0,0 +1,72 @@ +/* The Computer Language Shootout + http://shootout.alioth.debian.org/ + contributed by Isaac Gouy (Scala novice) +*/ + +object heapsort { + def main(args: Array[String]) = { + val n = toPositiveInt(args); + + val numbers = new Array[Double](n+1); + for (i <- Iterator.range(1,n+1)) + numbers(i) = generate(100.0); + + heapsort(n, numbers); + + Console.printf("{0,number,#.000000000}\n", numbers(n)); + } + + + def heapsort(n: Int, ra: Array[Double]): Unit = { + var l = 0; var j = 0; var ir = 0; var i = 0; + var rra = 0.0d; + + if (n < 2) return; + l = (n >> 1) + 1; + ir = n; + while (true) { + if (l > 1) { l = l-1; rra = ra(l); } + else { + rra = ra(ir); + ra(ir) = ra(1); + ir = ir-1; + if (ir == 1) { + ra(1) = rra; + return; + } + } + i = l; + j = l << 1; + while (j <= ir) { + if (j < ir && ra(j) < ra(j+1)) { j = j+1; } + if (rra < ra(j)) { + ra(i) = ra(j); + i = j; + j = j + i; + } + else j = ir + 1; + } + ra(i) = rra; + } + } + + + private val IM = 139968; + private val IA = 3877; + private val IC = 29573; + private var seed = 42; + + private def generate(max: Double) = { + seed = (seed * IA + IC) % IM; + max * seed / IM; + } + + + private def toPositiveInt(s: Array[String]) = { + val i = + try { Integer.parseInt(s(0)); } + catch { case _ => 1 } + if (i>0) i; else 1; + } + +} |