-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am Mittwoch, 12. Juni 2002 04:02 schrieb Richard A. O'Keefe:

> as Insertion Sort is a part
> of many advanced sorting algorithms.

i wrote "part" with reason.

>     If I had not done that, I'd need to check for j<= 0, which would make
> the implementation significantly slower.
>
> No, it wouldn't.  To start with, insertion sort should never be used for
> big arrays 

A lot of sorting algorithms speed up when you use insertion sort below a 
certain level. Quick sort, e.g.

> To continue, what if you have to sort an Array, which has a fixed size?

Well, Richard, I'm not saying I want to apply all my techniques in every 
situation. 

> But the really interesting thing about insertion sort is that you can
> get a perfectly suitable sentinel from the elements of the array itself.

Yep, that should do it. Nice idea.

> 	I don't think modifiying at: put: and so on is a serious option, as
> they're the very heart of these algorithms, modifying them would probably
> cost a lot of performance.
>
> Ahem.  If you are THAT worried about performance, you should not be
> sorting an OrderedCollection.  Look at the code for OrderedCollection>>at:
>
>     at: anInteger
> 	(anInteger < 1 or: [anInteger + firstindex - 1 > lastIndex])
> 	    ifTrue:  [self errorNoSuchElement[
> 	    ifFalse: [^array at: anInteger + firstIndex - 1]

geek! i had found out, and then modified my heap a little. now the array 
performs downheap and upheap itself, from firstIndex to lastIndex.
I think I'm faster than the default implementation in squeak. Do you have a 
benchmark at hand? Or a typical piece of code accessing a heap?

> 	Once for calculating index+1, and then the overhead of the
> 	method call would be serious, cos i found out that at:  index is
> 	a primitive, which is inlined.
>
> Not for OrderedCollections it isn't.  The version of #at: which Array
> (for example) inherits from Object is a primitive, but OrderedCollection
> overrides it with the method shown above, which is NOT a primitive.

Gep, just noticed. Brr...

>     For the fastest way to insertion sort an OrderedCollection in
> Smalltalk: 1.  copy the elements into an Array (just the right size!)
>     using array := oc asArray.
>
> 2.  sort the array using (the Smalltalk equivalent of) the C code isort()
>     I displayed above.
>
> 3.  stuff the array back into the OrderedCollection.

Why not placing the modifying code in the underlying array?
sic, the underlying array is exactly the same as the oc, except that it has a 
head and a tail. you could sort the underlying array from within the array, 
using sort from: to:. 

> The time you'll save by using a fast #at: will more than compensate for
> any speedup you'd have got by using a Sentinel,

i sure buy that. 

regards,

nick
- -- 
Going to church does not make a person religious, nor does going to
school make a person educated, any more than going to a garage makes a
person a car.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9BxwWc9uyCiO8RNQRAsIjAJ9TPKRFIRvytdzRa0QXMmpGZZ8FsACgmyJ0
TX0kMJETRfNBri5dF557FBo=
=+aWj
-----END PGP SIGNATURE-----