Re: more on stable sorting...

FROM : Dennis De Mars
DATE : Fri Nov 22 22:12:54 2002

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