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.
I copied over the code and adapted it to the settings
of SortPackage. It works fine:
(9) -> l := [4,3,2,1]
(9) [4,3,2,1]
Type: List(PositiveInteger)
(10) -> countingBubbleSort(l)$SortPackage(INT, LIST INT)
(10) [sorted= [1,2,3,4],exchanges= 6]
Type: Record(sorted: List(Integer),exchanges: NonNegativeInteger)
For details please see:
https://github.com/raoulb/fricas/commit/96cf7289d0ecab1049e86df27a4a566a52af3e1b
Why do I have to do package calling?
BTW1: I'll add an inplace operation too. Maybe even replacing this one?
BTW2: The code for UnaryRecursiveAggregate is missing. I'll have to see
if can implement something there.
BTW3: Maybe it would be possible to make counting versions of more
efficient sorting algorithms too. Should be easy for insertion sort
(not better than bubble sort) and possible merge sort at least.
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?
--
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.
