Sorting oddity - feature or ??

Hannes Hirzel hannes.hirzel.squeaklist at bluewin.ch
Wed May 1 17:00:42 UTC 2002


Bob Arning  <arning at charm.net> wrote:
> Hi all,
> 
> Is the following a known and accepted feature of our sorting algorithm?
> 
> [((1 to: 10000) collect: [ :x | x]) asSortedCollection] timeToRun ==> 98
> 
> [((1 to: 10000) collect: [ :x | 3]) asSortedCollection] timeToRun ==> 20826
> 
> Cheers,
> Bob

No, I don't think it is known and accepted.

Another test:
[((1 to: 10000) collect: [ :x | 10001 - x]) asSortedCollection]
timeToRun ==> 87



asSortedCollection

calls

newFrom: aCollection    "implemented in OrderedCollection"
	"Answer an instance of me containing the same elements as aCollection."

	| newCollection |
	newCollection _ self new: aCollection size.
	newCollection addAll: aCollection.
	^newCollection


And #addAll: is implemented in SortedCollection

addAll: aCollection
	aCollection size > (self size // 3)
		ifTrue:
			[aCollection do: [:each | self addLast: each].
			self reSort]
		ifFalse: [aCollection do: [:each | self add: each]].
	^ aCollection


which calls #add:

add: newObject
	^ super insert: newObject before: (self indexForInserting: newObject)

which finally calls
#insert:before:

and
#indexForInserting:


Two methods which are fairly complex and must contain an error
somewhere.

Are there sorting specialists out there?

Regards
Hannes



More information about the Squeak-dev mailing list