What is the most efficient way to sort an NSSet?

Question

What's the most efficient way to sort objects in an NSSet/NSMutableSet based on a property of the objects in the set? Right now the way I am doing it is by iterating through each object, add them to a NSMutableArray, and sort that array with NSSortDescriptor.

Answer 1

NSSet is a collection of unordered objects. Looking at apple references Arrays are ordered collections.

Looking at NSArray there is a discussion with examples of sorting at http://developer.apple.com/documentation/Cocoa/Conceptual/Collections/Articles/sortingFilteringArrays ...

Example from the link:

NSInteger alphabeticSort(id string1, id string2, void *reverse)
{
    if ((NSInteger *)reverse == NO) {
        return [string2 localizedCaseInsensitiveCompare:string1];
    }
    return [string1 localizedCaseInsensitiveCompare:string2];
}

---

// assuming anArray is array of unsorted strings

NSArray *sortedArray;

// sort using a selector
sortedArray =
  [anArray sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];

// sort using a function
int reverseSort = NO;
sortedArray =
  [anArray sortedArrayUsingFunction:alphabeticSort context:&reverseSort];

Answer 2

What you have is probably your best option, as adding to an array (especially since you know the size it needs to be from the start) is O(n) and then sorting will be O(n log(n)), so you will end up with just O(n log(n)) for the entire thing

try using

[[mySet allObjects] sortedArrayUsingDescriptors:descriptors];

Answer 3

The "most efficient way" to sort a set of objects varies based on what you actually mean. The casual assumption (which the previous answers make) is a one-time sort of objects in a set. In this case, I'd say it's pretty much a toss-up between what @cobbal suggests and what you came up with — probably something like the following:

NSMutableArray* array = [NSMutableArray arrayWithCapacity:[set count]];
for (id anObject in set)
    [array addObject:anObject];
[array sortUsingDescriptors:descriptors];

(I say it's a toss-up because @cobbal's approach creates two autoreleased arrays, so the memory footprint doubles. This is inconsequential for small sets of objects, but technically, neither approach is very efficient.)

However, if you're sorting the elements in the set more than once (and especially if it's a regular thing) this is definitely not an efficient approach. You could keep an NSMutableArray around and keep it synchronized with the NSSet, then call -sortUsingDescriptors: each time, but even if the array is already sorted it will still require N comparisons.

Cocoa by itself just doesn't provide an efficient approach for maintaining a collection in sorted order. Java has a TreeSet class which maintains the elements in sorted order whenever an object is inserted or removed, but Cocoa does not. It was precisely this problem that drove me to develop something similar for my own use.

As part of a data structures framework I inherited and revamped, I created a protocol and a few implementations for sorted sets. Any of the concrete subclasses will maintain a set of distinct objects in sorted order. There are still refinements to be made — the foremost being that it sorts based on the result of -compare: (which each object in the set must implement) and doesn't yet accept an NSSortDescriptor. (A workaround is to implement -compare: to compare the property of interest on the objects.)

One possible drawback is that these classes are (currently) not subclasses of NS(Mutable)Set, so if you must pass an NSSet, it won't be ordered. (The protocol does have a -set method which returns an NSSet, which is of course unordered.) I plan to rectify that soon, as I've done with the NSMutableDictionary subclasses in the framework. Feedback is definitely welcome. :-)