-- -*- mode: eiffel -*-
-- $Id: heapsort.se,v 1.1 2001/05/21 18:18:41 doug Exp $
-- http://www.bagley.org/~doug/shootout/

class HEAPSORT

creation make

feature

   make is
      local
     array: ARRAY[DOUBLE]
     n: INTEGER
      do
     n := argument(1).to_integer
     !!array.make(1, n)
     fill_array(array)
     sort_array(n, array)
     io.put_string(array.item(n).to_string_format(10))
     io.put_new_line
      end
   
   sort_array(n: INTEGER; ra: ARRAY[DOUBLE]) is
      local
     i, j, ir, l: INTEGER
     rra: DOUBLE
     done: BOOLEAN
      do
     j := 0
     i := 0
     rra := 0.0
     ir := n
     l := n // 2
     done := false
     
     from until done loop
        if l > 1 then
           l := l - 1
           rra := ra.item(l)
        else
           rra := ra.item(ir)
           ra.put(ra.item(1), ir)
           ir := ir - 1
           if ir = 1 then
          ra.put(rra, 1)
          -- should throw exception out of here instead of 
          -- using boolean
          done := true
           end
        end
        
        if not done then
           i := l
           j := l * 2
           
           from until j > ir loop
          if (j < ir) and (ra.item(j) < ra.item(j+1)) then
             j := j + 1
          end
          if rra < ra.item(j) then
             ra.put(ra.item(j), i)
             i := j
             j := j + i
          else
             j := ir + 1
          end
           end
           ra.put(rra, i)
        end
     end
      end


   fill_array(an_array: ARRAY[DOUBLE]) is
      local
     rand: RANDOMNUMBER
     index: INTEGER
      do
     from
        !!rand.make
        index := an_array.lower
     until
        index > an_array.upper
     loop
        an_array.put(rand.next(1), index)
        index := index + 1
     end
      end

end