> > 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.
Yes. But the only essential thing I need to know about is the number of transpositions and use this. > Counting exchanges gives length > of some string of transpositions which mutiplied give > sequence treated as a permutation. Yes. And I need to bring this specific permutation back to the identity 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. It does, because I need to adapt the overall sign of an expression depending on the numbers of interchanges done while putting it into canonical form. The transformation has not to be unique but just well defined as long as the result is unique. Another nice example would be creation and annihilation operators in quantum mechanics. When we try to put a string of operators into normal form, then the expression picks up a sign change for each transposition done. > Concerning sign, we already have function to compute sign > of a permutation. Could you maybe make an example of how to use this? Is is possible to use this for general Lists with arbitrary Elements and possibly a user specified Order relation? > Computing sign and sorting together may be convenient > for user and may serve as an optimization. It really is, although I admit the user case is special. > However, sign can be computed in linear time, sorting is > n*log(n) while bubble sort is quadratic. Yes, in theory this is of course true. However this feature is supposed to be used only for relatively short lists. > 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. Right. Despite this limitation I consider the feature to be very useful. -- 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.
