Re: more on stable sorting...
Re: more on stable sorting...
- Subject: Re: more on stable sorting...
- From: Sam Griffith <email@hidden>
- Date: Fri, 22 Nov 2002 09:01:39 -0600
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@hidden
Web site:
http://homepage.mac.com/staypufd/index.html
On 11/22/2002 5:09 AM, "Philippe Mougin" <email@hidden> 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@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.