Re: more on stable sorting...
Re: more on stable sorting...
- Subject: Re: more on stable sorting...
- From: "Philippe Mougin" <email@hidden>
- Date: Fri, 22 Nov 2002 12:09:39 +0100
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.