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.
> This is the case for example when working with skew-symmetric
> expressions. Hence I would want to implement the following
> function (names are up for discussion):
>
> countingBubbleSort : (A, (S, S) -> Boolean) -> Record(sorted:A,
> exchanges:NNI)
>
> I know there is such a code in the Clifford Domain,
> in the file "clifford.spad.pamphlet" at line 933ff.
Hmm, I wonder about mathematical definition of your operation.
'CliffordAlgebra' and skew-symmetic operations use sign (parity),
which is well defined. Counting exchanges gives length
of some string of transpositions which mutiplied give
sequence treated as a permutation. There are some uses
of length, but one has to be careful to compute it
correctly, because using different string of transpositions
can give different length. It is not clear for me if
bubble sort computes useful length or not.
Concerning sign, we already have function to compute sign
of a permutation. Computing sign and sorting together
may be convenient for user and may serve as an optimization.
However, sign can be computed in linear time, sorting is
n*log(n) while bubble sort is quadratic. So using
counting bubble sort for such optimization make sense only
for very small n, which is the case for CliffordAlgebra
but not for general case.
>
> BTW1: I'll add an inplace operation too. Maybe even replacing this one?
>
>
> Another question: what happens here? Is this a bug?
>
> (37) -> l := [4,2,2,2,3,3,1]
>
> (37) [4,2,2,2,3,3,1]
> Type: List(PositiveInteger)
> (38) -> sort! l
>
> (38) [1,2,2,2,3,3,4]
> Type: List(PositiveInteger)
> (39) -> sort! l
>
> (39) [4]
> Type: List(PositiveInteger)
>
> Why can I not call it twice?
Ralf already answered that, but let me add that 'sort!' is
not considered "in place" but "destructive". See:
(1) -> l := [4,2,2,2,3,3,1]
(1) [4,2,2,2,3,3,1]
Type: List(PositiveInteger)
(2) -> sort! l
(2) [1,2,2,2,3,3,4]
Type: List(PositiveInteger)
(3) -> l
(3) [4]
Type: List(PositiveInteger)
So, after call to 'sort!' the 'l' variable contains trash, while
the correct result is given by return value. Some operations
(typically ones working on vectors and matrices) really are
"in place". Other destroy their argument. However, normally
return value contains the result and should be used.
--
Waldek Hebisch
[email protected]
--
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.
