[VAST] SortedCollection

[geoff]

I wanted to try different sorts with SortedCollection. To change the
sorting method, I modified 'SortedCollection>>#addAllSelectionSorted:'. The
complete method for a selection sort is:

addAllSelectionSorted: aCollection
"Answer aCollection having added each element of aCollection to the
receiver."

| arr currentIndex collSize iMin i temp |

elements := (elements asOrderedCollection addAll: aCollection) asArray.
size := elements size.

arr := elements.
currentIndex := 1.
collSize := arr size.

[ currentIndex < collSize ] whileTrue: [
iMin := currentIndex.
i := currentIndex + 1.
[ i <= collSize ] whileTrue: [
(sortBlock value: (arr at: iMin) value: (arr at: i))
ifTrue: [ iMin := i ].
i := i + 1.
].

temp := arr at: currentIndex.
arr at: currentIndex put: (arr at: iMin).
arr at: iMin put: temp.
currentIndex := currentIndex + 1.
].

^aCollection

. . . I noticed that 'SortedCollection>>#addAll:' also uses the default
sort. If one subclassed SortedCollection, I'm curious what methods others
would override to implement a new sort?

--g

[Marten]

There is normally no need to subclass SortedCollection. To get a
different way of sorting you may do code like:


aSortedCollection := SortedCollection sortBlock: [ :a :b | a asInteger
< b asInteger ]

aSortedCollection
add: anInstance ;
add: anotherInstance ;
....

depending on the Smalltalk you actually use ...

[geoff]

Sorry, I do not understand your answer. I was commenting on changing the
default sorting method, a bubble sort, to a different sort, eg a selection
sort.

Your answer covers sort blocks. The sort block, '[ :a :b | a asInteger < b
asInteger ]', would use the bubble sort.

--g

[Randal L. Schwartz]

geoff> Sorry, I do not understand your answer. I was commenting on
geoff> changing the default sorting method, a bubble sort, to a
geoff> different sort, eg a selection sort.

It's very unlikely that VAST uses a "bubble" sort. What's your evidence
for this?

Even the original Smalltalk-80 used a fairly efficient sort.

[John Brant]

Post by Randal L. Schwartz
geoff> Sorry, I do not understand your answer. I was commenting on
geoff> changing the default sorting method, a bubble sort, to a
geoff> different sort, eg a selection sort.
It's very unlikely that VAST uses a "bubble" sort. What's your evidence
for this?

VAST uses a heap sort but has names like bubbleUp*/Down* so people
incorrectly think it is a bubble sort.


John Brant

[geoff]

Post by John Brant
VAST uses a heap sort

That is interesting! When one sees methods like 'bubbleUp*/Down*' then I
think bubble sort.

I searched the docs and image but did not find the words 'heap sort'. I'm
going to spend some time running SortedCollection through the debugger.

It would be interesting to be able to plugin diffeerent sorting methods as
the other poster suggested.

--g

[John Brant]

Post by geoff

Post by John Brant
VAST uses a heap sort

That is interesting! When one sees methods like 'bubbleUp*/Down*' then I
think bubble sort.
I searched the docs and image but did not find the words 'heap sort'. I'm
going to spend some time running SortedCollection through the debugger.

I don't see that they use "heap sort" together. However, several
comments talk about a heap, and if you read the code (or the comments in
#sort), you can see that it is a heap sort.


John Brant

[Peter Kenny]

geoff wrote...

Post by geoff
I wanted to try different sorts with SortedCollection. To change the
sorting method, I modified 'SortedCollection>>#addAllSelectionSorted:'.

geoff

I don't know VAST, so this may be off-beam, but it may be interesting that
the current version of Dolphin Smalltalk has pluggable sort algorithms. The
methods of SortedCollection do not do any sorting; it is all delegated to an
instance of the class SortAlgorithm, the appropriate SortAlgorithm being an
instvar of the collection (incidentally, the sort block is an instvar of the
algorithm, which tidies things up a bit). There are subclasses of
SortAlgorithm for each well-known method. Depending on how VAST organises
things, e.g. whether there is just one instance method which implements the
sort algorithm, it may be possible to reproduce something like this
organisation; it seems cleaner somehow than having a special instance method
for each sort.

BTW, are you sure that bubble sort is the default in VAST? If so, I can see
why you would want to try alternatives!

Peter Kenny