On 10/20/2012 10:31 PM, someone wrote:
> I'd like to propose a simple extension of the common
> bubble sort algorithm. Sometimes it is necessary to
> know how many exchanges took place during the sorting.
There would be also another option to count the number of swappings.
If you look at the definition of the SortingPackage, it has two
parameters. One is the Aggregate object (List in your case) over which
the sorting is done and the first argument specifies the element type of
the entries.
Looking at the source code reveals that there is a swap! function that
is called each time two elements have to be exchanged. So another idea
to achieve counting, would be to create a "wrapper" domain around your
aggregate.
---rhxBEGIN mya.spad
)abbrev domain MYA MyA
Z ==> Integer
ACat ==> Join(IndexedAggregate(Integer, S), finiteAggregate,
shallowlyMutable)
MyA(S: Type, A: ACat, f: () -> Void): ACat with
coerce: A -> %
coerce: % -> A
== A add
coerce(a: A): % == a pretend %
coerce(x: %): A == x pretend A
swap!(x: %, i: Z, j: Z): Void == (f(); swap!(x::A, i, j))
---rhxEND mya.spad
Then in the interpreter say...
(1) -> )compile mya.spad
(1) -> Z := Integer; LZ := List Z
(1) List(Integer)
Type:
Type
(2) -> l: LZ := [4,3,2,1,0]
(2) [4,3,2,1,0]
Type: List(Integer)
(3) -> cc:Record(cnt: Z) := [0]
(3) [cnt= 0]
Type: Record(cnt: Integer)
(4) -> countx(): Void == cc.cnt := cc.cnt+1
Function declaration countx : () -> Void has been added to
workspace.
Type: Void
(5) -> MA := MyA(Z, LZ, countx)
Compiling function countx with type () -> Void
(5) MyA(Integer,List(Integer),theMap(*0;countx;1;frame1))
Type: Type
(6) -> bubbleSort!(l::MA)$SortPackage(Z, MA)::LZ
(6) [0,1,2,3,4]
Type: List(Integer)
(7) -> cc
(7) [cnt= 10]
Type: Record(cnt: Integer)
Of course, that's quite a lot of overhead for such a simple task, but I
hope I could demonstrate that SPAD allows for more abstract ways of
programming. There is no need to implement every little function (and
thus perhaps partly copying code -- which makes maintenance a nightmare).
SPAD is more about writing generic functions and then putting together
all the pieces in order to achieve what one wants.
Ralf
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
