[Shootout-list] Ruby heapsort correction

[Jabari Zakiya]

Fully accurate correction to Ruby heapsort benchmark.

Problem:

In previous modification to originally submitted code I
overlooked the hardwiring in the code of the first index
starting at array[1]. Since Ruby is zero-index based, this
causes the array to not be fully sorted, as it misses using
the first array element array[0]. But since only the last
array element is printed out, if you don't check the
whole sorted array this problem might not be seen if
the first array element isn't the largest array value.

I believe this problem exists for all the other languages
which use zero-based array indexing, such as Forth, but I
haven't checked yet.

Solution:

The simple solution in Ruby is to append a dummy element to the
front of the input array with: ra.unshift(nil).

This shifts the input data from indices 0..n-1 to 1..n
and allows the rest of the code to be used without modification.

A corresponding de-shifting of the array data back to indices
0..n-1 is needed by perfroming: ra.shift, before returning.

I'll do a native zero-index based index version later.

Jabari Zakiya

def heapsort(n, ra)
    j =3D i =3D rra =3D 0
    l =3D (n >> 1) + 1
    ir =3D n
    ra.unshift(nil) # append a dummy value to front of array
    while (1)
        if l > 1
           rra =3D ra.at(l -=3D 1)
        else
           rra =3D ra.at(ir)
           ra[ir] =3D ra.at(1)
           if (ir -=3D 1) =3D=3D 1
               ra[1] =3D rra
               ra.shift  # create originally sized array
               return
           end
        end
        i =3D l
        j =3D l << 1
        while  j <=3D ir
            if j < ir and ra.at(j) < ra.at(j+1)
               j +=3D 1
            end
            if rra < ra.at(j)
               ra[i] =3D ra.at(j)
               j +=3D (i =3D j)
            else
               j =3D ir + 1
            end
        end
        ra[i] =3D rra
    end
end

N =3D Integer(ARGV.shift || 1)
ary =3D Array.new(N) { gen_random(1.0) }
heapsort(N, ary)
printf "%.10f\n", ary.last

--=20
___________________________________________________________
Sign-up for Ads Free at Mail.com
http://promo.mail.com/adsfreejump.htm