> 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.
Let me first propose another method than adding a new function to the
sorting package.
The assumption is that each time the comparison function is called that
costs unit. With the example below, I count every call to the comparison
function. Under the additional assumption that each time the comparison
function yields true, a swap happens, you can easily modify the example
to count the exchanges. Simply use
ltCount2(x: Z, y: Z): Boolean == (r:Boolen := x<y; if r then c.cnt :=
c.cnt+1; r)
Ralf
(1) -> Z := Integer
(2) -> LZ := List Z
(3) -> c:Record(cnt: Z) := [0]
(3) [cnt= 0]
Type: Record(cnt: Integer)
(4) -> ltCount(x: Z, y: Z): Boolean == (c.cnt := c.cnt+1; x<y)
Function declaration ltCount : (Integer,Integer) -> Boolean has been
added to workspace.
(5) -> l: LZ := [4,3,2,1,0]
(5) [4,3,2,1,0]
Type: List(Integer)
(6) -> bubbleSort!(l, ltCount)$SortPackage(Z, LZ)
Compiling function ltCount with type (Integer,Integer) -> Boolean
(6) [0,1,2,3,4]
Type: List(Integer)
(7) -> c
(7) [cnt= 15]
Type: Record(cnt: Integer)
--
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.
