Re: more on stable sorting...
Re: more on stable sorting...
- Subject: Re: more on stable sorting...
- From: Dennis De Mars <email@hidden>
- Date: Fri, 22 Nov 2002 13:12:54 -0800
Granted, stable sorts are a standard tool and it would be very useful
if NSArray directly supported them.
The current sorting selectors still have to be supported, so I would
suggest adding to the current set another set with a "stable:"
parameter. So for instance, in addition to the current selector
- (NSArray *)sortedArrayUsingSelector:(SEL)comparator
which would do the same thing it does now, you would also have:
- (NSArray *)sortedArrayUsingSelector:(SEL)comparator
stable:(BOOL)stableSort
If you use the latter form, then specifying YES for the last parameter
would use a stable sort and NO would use the regular (faster) sort
algorithm. This has the advantage that if you need to choose whether to
do a stable sort at runtime you can do it with one statement rather
than branching to two different statements.
Can be done with a category but it would probably be more efficient if
Apple built it in. (I like your idea of dumping the NSArray into a C
array and running a BSD function on it, that would be much faster than
the way I was thinking of doing it).
- Dennis D.
On Friday, November 22, 2002, at 03:09 AM, Philippe Mougin 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.