Re: more on stable sorting...

FROM : Sam Griffith
DATE : Fri Nov 22 16:01:39 2002

Can on eof you guys write a category to do just what you said below by
having a - (NSArray*)stableSort: (NSArray*) method in that category.  And
then give out the source to all of us.... In the spirit of community...


--
Sam Griffith Jr.
email:      <email_removed>
Web site:  http://homepage.mac.com/staypufd/index.html

On 11/22/2002 5:09 AM, "Philippe Mougin" <<email_removed>> wrote:

> Stable sorting is usually considered as the canonical solution for the
> problem at hand. It is used in scientific and business data analysis tools
> to let users do incremental, interactive, multi-criteria sorting. There are
> very good stable sorting algorithms. For instance the BSD mergesort()
> function is very fast (in many cases, nearly as fast as a quicksort) and is
> stable (it requires more memory than a quicksort, though). It operates on C
> arrays but it's easy to use it with an NSArray: put the elements of your
> NSArray in a C array using the -getObjects: method, use mergesort(), and put
> back the result in an NSArray.
>
> Nevertheless, it would be nice, as pointed by Ondra, to have stable sorting
> directly available on the NSArray sorting API. It would be easier to use,
> and faster (avoiding copy operations). Instead of a flag in the API or in
> the defaults for requesting "stable" sorting, I think it would be better to
> have the choice between sorting algorithms. There are several well-known and
> documented sorting algorithms out there, each with several specific
> properties (not just stableness, but also complexity, memory usage etc...).
> The API should make reference to the algorithm used: the developer could
> then consult the literature on this subject and decide which algorithm to
> choose, depending on his requirements/context.
> At the very least, we should have the choice between quick sort (this is
> probably the one currently used) and merge sort. So instead
> of -sortedArrayUsingSelector:  we could have, for
> xample,  -quickSortedArrayUsingSelector: and -mergeSortedArrayUsingSelector:
>
> Phil
>
>> 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.
> _______________________________________________
> 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.