Heapsort
The following package demonstrates how classical imperative algorithm
can be written in Spad. It uses SingleInteger? that is type of machine
sized integer, which has limited precision but allows better speed
than Integer (normal integer type with unlimited precision). Note that
integer constants have type Integer so to obtain constant of type
SingleInteger? we need the following:
qconvert(2)@SingleInteger?
Constants 0 and 1 are special, they are taken from appropriate domain,
so we can write them as-is.
Also, note that PrimitiveArray? is 0 based, while some other array types
like Vector are 1 based.
fricas
(1) -> <spad>
fricas
)abbrev package HEAPSRT Heapsort
Heapsort : Exports == Implementation where
Val ==> SingleInteger
V ==> PrimitiveArray SingleInteger
conv(x) ==> qconvert(x)@SingleInteger
Exports ==> with
heapsort : V -> V
gen_random : Integer -> Integer
gen_random_array : (NonNegativeInteger, Integer) -> V
Implementation ==> add
LAST : Integer := 42 ;
IM ==> 139968
IA ==> 3877
IC ==> 29573
gen_random( n ) ==
qr := divide(LAST * IA + IC, IM)
LAST := qr.remainder
qr := divide(n * LAST, IM)
qr.quotient
heapsort(ra) ==
n : SingleInteger := qconvert(#ra)@SingleInteger
rra: Val := 0
i : SingleInteger := -1
j : SingleInteger := -1
l : SingleInteger := n quo qconvert(2)@SingleInteger
ir : SingleInteger := n - 1
repeat
if 0 < l then
l := l - 1
rra := ra(l)
else
rra := ra(ir)
ra(ir) := ra(0)
ir := ir - 1
if ir = 0 then
ra(0) := rra
return ra
i := l
j := 1 + l*qconvert(2)@SingleInteger
while not(ir < j) repeat
if (j < ir) and ( ra(j) < ra(j + 1)) then
j := j + 1
if rra < ra(j) then
ra(i) := ra(j)
i := j
j := j + i + 1
else
j := ir + 1
ra(i) := rra
gen_random_array(n, m) ==
my_tab : V := new(n, 0)
for i in 0..(n - 1) repeat
my_tab(i) := conv(gen_random(m))
my_tab</spad>
fricas
Compiling FriCAS source code from file
/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3302976695248515676-25px001.spad
using old system compiler.
HEAPSRT abbreviates package Heapsort
------------------------------------------------------------------------
initializing NRLIB HEAPSRT for Heapsort
compiling into NRLIB HEAPSRT
processing macro definition IM ==> 139968
processing macro definition IA ==> 3877
processing macro definition IC ==> 29573
compiling exported gen_random : Integer -> Integer
Time: 0 SEC.
compiling exported heapsort : PrimitiveArray SingleInteger -> PrimitiveArray SingleInteger
Time: 0.01 SEC.
compiling exported gen_random_array : (NonNegativeInteger,Integer) -> PrimitiveArray SingleInteger
Time: 0 SEC.
(time taken in buildFunctor: 0)
;;; *** |Heapsort| REDEFINED
;;; *** |Heapsort| REDEFINED
Time: 0 SEC.
Warnings:
[1] gen_random: remainder has no value
[2] gen_random: quotient has no value
[3] heapsort: l has no value
[4] heapsort: ir has no value
[5] heapsort: j has no value
[6] heapsort: i has no value
Cumulative Statistics for Constructor Heapsort
Time: 0.02 seconds
finalizing NRLIB HEAPSRT
Processing Heapsort for Browser database:
--->-->Heapsort(constructor): Not documented!!!!
--->-->Heapsort((heapsort ((PrimitiveArray (SingleInteger)) (PrimitiveArray (SingleInteger))))): Not documented!!!!
--->-->Heapsort((gen_random ((Integer) (Integer)))): Not documented!!!!
--->-->Heapsort((gen_random_array ((PrimitiveArray (SingleInteger)) (NonNegativeInteger) (Integer)))): Not documented!!!!
--->-->Heapsort(): Missing Description
; compiling file "/var/aw/var/LatexWiki/HEAPSRT.NRLIB/HEAPSRT.lsp" (written 30 NOV 2024 04:25:15 PM):
; wrote /var/aw/var/LatexWiki/HEAPSRT.NRLIB/HEAPSRT.fasl
; compilation finished in 0:00:00.024
------------------------------------------------------------------------
Heapsort is now explicitly exposed in frame initial
Heapsort will be automatically loaded when needed from
/var/aw/var/LatexWiki/HEAPSRT.NRLIB/HEAPSRT
Check it:
fricas
a1 := gen_random_array(17, 77)
Type: PrimitiveArray
?(SingleInteger
?)
fricas
heapsort(a1)
Type: PrimitiveArray
?(SingleInteger
?)