login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

## 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.

)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
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
   Compiling FriCAS source code from file
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.01 SEC.
compiling exported heapsort : PrimitiveArray SingleInteger -> PrimitiveArray SingleInteger
Time: 0.02 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.03 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 09 SEP 2015 01:14:19 PM):
; /var/aw/var/LatexWiki/HEAPSRT.NRLIB/HEAPSRT.fasl written
; compilation finished in 0:00:00.050
------------------------------------------------------------------------
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)
 (1)
Type: PrimitiveArray?(SingleInteger?)
fricas
heapsort(a1)
 (2)
Type: PrimitiveArray?(SingleInteger?)

 Subject:   Be Bold !! ( 14 subscribers )