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.

(1) -> <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 SEC.

   compiling exported heapsort : PrimitiveArray SingleInteger -> PrimitiveArray SingleInteger
Time: 0 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 25 NOV 2024 05:30:42 PM):

; wrote /var/aw/var/LatexWiki/HEAPSRT.NRLIB/HEAPSRT.fasl
; compilation finished in 0:00:00.020
------------------------------------------------------------------------
   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:

a1 := gen_random_array(17, 77)

(1)

heapsort(a1)

(2)