bench/shootout/heapsort.ruby

   1 #!/usr/bin/ruby
   2 # -*- mode: ruby -*-
   3 # $Id: heapsort.ruby,v 1.5 2005-04-14 15:59:37 igouy-guest Exp $
   4 #
   5 # The Great Computer Language Shootout
   6 # http://shootout.alioth.debian.org/
   7 #
   8 # modified by Jabari Zakiya
   9
  10 IM = 139968
  11 IA =   3877
  12 IC =  29573
  13
  14 $last = 42.0
  15 def gen_random (max) (max * ($last = ($last * IA + IC) % IM)) / IM end
  16
  17 def heapsort(n, ra)
  18     j = i = rra = 0
  19     l = (n >> 1) + 1
  20     ir = n - 1
  21
  22     while (1) do
  23         if (l > 1) then
  24             rra = ra.at(l -= 1)
  25         else
  26             rra = ra.at(ir)
  27             ra[ir] = ra.at(1)
  28             if ((ir -= 1) == 1) then
  29                 ra[1] = rra
  30                 return
  31             end
  32         end
  33         i = l
  34         j = l << 1
  35         while (j <= ir) do
  36             if ((j < ir) and (ra.at(j) < ra.at(j+1))) then
  37                 j += 1
  38             end
  39             if (rra < ra.at(j)) then
  40                 ra[i] = ra.at(j)
  41                 j += (i = j)
  42             else
  43                 j = ir + 1
  44             end
  45         end
  46         ra[i] = rra
  47     end
  48 end
  49
  50 N = Integer(ARGV.shift || 1)
  51 ary = Array.new(N) { gen_random(1.0) }
  52
  53 heapsort(N, ary)
  54
  55 printf "%.10f\n", ary.last