[Shootout-list] Ruby heapsort correction
Jabari Zakiya
jzakiya@mail.com
Thu, 14 Apr 2005 18:30:23 -0500
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