Re: NSArray merge sorting
Re: NSArray merge sorting
- Subject: Re: NSArray merge sorting
- From: David Scheidt <email@hidden>
- Date: Mon, 20 Apr 2009 21:06:55 -0400
On Apr 20, 2009, at 8:39 PM, Jonathan Hess wrote:
On Apr 20, 2009, at 5:32 PM, Greg Guerin wrote:
Would NSSet cut the mustard here?
NSArray allows duplicate items; NSSet does not. What do you
propose happen if one or both NSArray inputs have items that
compare as equal?
Algorithmically speaking, a merge sort from two inputs into a new
output seems pretty simple. Simply choose the lesser of the two
available next-items and append it to the new array. Or if both
next-items are equal, choose one arbitrarily.
You should probably choose the one that came first in the original
array. Merge sort should be order preserving, and even though the
objects are ordered the same with respect to the comparison
function, their identities my be different and their relative
ordering should be preserved.
This is what computer scientists call a "stable" sort. Handy if you
want to provide a list of names that's sorted by key1, and if key1 is
identical, by key2. (last name, then first name, then ID number, for
example.)
I'm prefectly capable of writing a merge sort. It's just that it
seemed like a pretty basic function, which I'm going to use what I'd
have thought was a pretty common reason (merging two arrays of strings
as possible values for NSComboBoxes), and if Apple had gone to the
trouble of writing one, I wanted to use it. Apple's code tends to be
faster than the stuff I write, for one thing, and it gets debugged by
more people.
My quick hack for avoiding this until I wrote a
mergesortWithSelector:RemoveDuplicates category on NSArray was to
stick the two lists into an NSMutableSet, and then put them into an
NSMutableArray and sort that with sortUsingSelector:. That works
fine, and seems fast enough (though I didn't instrument it), but
offends my sense of elegance.
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden