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.

spad
)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
   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.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)

\label{eq1}\left[{28}, \:{56}, \:{49}, \:{61}, \:{41}, \:{11}, \:{44}, \:{2
4}, \: 0, \:{41}, \:{15}, \:{53}, \:{36}, \:{25}, \:{50}, \:{1
4}, \:{65}\right](1)
Type: PrimitiveArray?(SingleInteger)
fricas
heapsort(a1)

\label{eq2}\left[ 0, \:{11}, \:{14}, \:{15}, \:{24}, \:{25}, \:{28}, \:{3
6}, \:{41}, \:{41}, \:{44}, \:{49}, \:{50}, \:{53}, \:{56}, \:{6
1}, \:{65}\right](2)
Type: PrimitiveArray?(SingleInteger)




  Subject:   Be Bold !!
  ( 12 subscribers )  
Please rate this page: