more on stable sorting...

FROM : Steve Mykytyn
DATE : Tue Nov 19 21:20:53 2002

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_removed>              http://www.ocs.cz
> private        <email_removed>            http://www.ocs.cz/oc
_______________________________________________
cocoa-dev mailing list | <email_removed>
Help/Unsubscribe/Archives: http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.