more on stable sorting...
more on stable sorting...
- Subject: more on stable sorting...
- From: Steve Mykytyn <email@hidden>
- Date: Tue, 19 Nov 2002 12:20:53 -0800
thanks to Ondra, John, and Dan for their thoughtful responses on the
stable sorting issue...
I think it would be a good idea to submit a feature request on stable
sorting - at the least the Cocoa docs should say the sorts are NOT
stable, at best having a way to optionally specify a stable sort would
be very nice.
Although any sort can be made stable, there is a cost in time and/or
memory. The best workaround for my purpose is to keep a small
persistent list of the most recently sorted columns, and use those to
break ties as needed. But a good deal of complexity, either user
interface or coding, is introduced with any solution i've come up with
so far. I'd gladly endure whatever overhead stable sorting introduced
to keep the overall code simpler...
I suppose a lot of this comes down to what a reasonable user would
expect when first sorting on one column, then another.
On Tuesday, November 19, 2002, at 05:17 AM, Ondra Cada wrote:
On Tuesday, Nov 19, 2002, at 03:53 Europe/Prague, John C. Randolph
wrote:
I wouldn't call it a bug. If you return NSOrderedSame, I'd say it's
fair to insert the two elements in question in either order. It
sounds like in your situation, they're not *really* the same. For
the example you give, your compare method should check both criteria.
It's a bit more subtle. Programmer's POV of course there's no real
difference: you either sort by more keys or not, and save some
(generally negligible) performance gain, stable or non-stable sorting,
all the same.
The advantage of stable sorting algorithm comes from the user's POV:
you don't need to have any GUI for multi-key sorting, and *still* you
can, effectively, do that. Of course again this *can* be achieved
programmatically, but the vast advantage of a stable NSArray sorting
would the that it would just work for any app, regardless its
programmer even considered it or not.
That's why I think a feature request might be a right way (of course,
a bug report would be out of order -- there's no bug, we are speaking
of a possible feature to be added). Also, I am not *that* an expert of
sorting algorithms: although I am quite positive there is a stable
sorting algorithm which won't be slower than anything which is
actually used (qsort?), I might be wrong there.
If there is no stable algorithm quick enough, it might be best if it
was externally settable by a default, something like
com.apple.stableArraySortingAlgorithm NO/YES.
---
Ondra Cada
OCSoftware: email@hidden http://www.ocs.cz
private email@hidden http://www.ocs.cz/oc
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.