Re: more on stable sorting...
Re: more on stable sorting...
- Subject: Re: more on stable sorting...
- From: Buddy Kurz <email@hidden>
- Date: Wed, 20 Nov 2002 07:54:28 -0800
A couple of decades ago when I was writing database packages, I would
append the original record index as the last sort criteria. There was
little overhead having an integer compare as the tie breaker. I would
expect this would be a good solution when re-sorting an array of
objects since the sort algorithm would have no knowledge of the method
used to compare two objects on a previous sort.
My $.02: I would rather not see an option for a default for stable
sorting/unstable sorting.
On Tuesday, November 19, 2002, at 12:20 PM, Steve Mykytyn wrote:
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.
_______________________________________________
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.