> > 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.
But the spaws need necessarily not to exchange neighbouring items.
So we would have to increment not by 1 but by 2*k+1 with k the number
of element inbetween the two swapped ones.
If we use bubbleSort for the underlying sorting, then its ok.
> 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)
Do you really count exchanges here? Because then this count is wrong.
(5) -> l := [4,3,2,1,0]
(5) [4,3,2,1,0]
Type: List(NonNegativeInteger)
(6) -> countingBubbleSort(l, <)$SortPackage(INT, LIST INT)
(6) [sorted= [0,1,2,3,4],exchanges= 10]
Type: Record(sorted: List(Integer),exchanges: NonNegativeInteger)
Anyway, this type of function decoration is a nice trick!
Thanks for making the example.
--
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.
