Re: more on stable sorting...

FROM : Buddy Kurz
DATE : Wed Nov 20 16:54:28 2002

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_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.
_______________________________________________
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.