Array Self-Sorting

The current Dr. Touch Part that I am working on for my store is about quickly clustering POIs if they would be too close together on a MKMapView. For this purpose I need to calculate distances between all annotation pins and add to this the distances to all newly found clusters. Currently this involves resorting the whole list of distances multiple times. So I put my thinking hat on and built this category extension for NSMutableArray to add numbers of objects in the correct place according to the specified sort order.

To cut down on search time for the insertion point I am using a “divide an conquer” approach. Split the search range in half and check if the value at this index is bigger or smaller than the one I am trying to insert. Continue to divide until the length of my search range is 0. At that point I have found the appropriate place for the insertion.

This approach means that for 1000 values/objects in the array only 10 comparisons are necessary. This is most likely way less than if you are constantly creating sorted copies of the array with one of the three standard sorting methods.

NSMutableArray+SelfSorting.h

#import 
 
@interface NSMutableArray (SelfSorting)
 
- (void)insertNumberAtSortedLocation:(NSNumber *)aNumber;
 
@end

To test the algorithm we first create it with NSNumber instances in mind. Later we can generify the approach to be used on any kind of object (as long as it implements the compare: method). So for self-sorting numbers we implement:

#import "NSMutableArray+SelfSorting.h"
 
@implementation NSMutableArray (SelfSorting)
 
- (void)insertNumberAtSortedLocation:(NSNumber *)aNumber
{
	NSUInteger count = [self count];
 
	// if there are no contents yet, simply add it
	if (!count)
	{
		[self addObject:aNumber];
		return;
	}
 
	NSRange searchRange;
	searchRange.location = 0;
	searchRange.length = count;
 
 
	// bubble sort finding of insert point
	do
	{
		NSInteger index = searchRange.location + searchRange.length/2;
 
		NSNumber *testNumber = [self objectAtIndex:index];
 
		switch ([aNumber compare:testNumber])
		{
			case NSOrderedAscending:
			{
				//searchRange.length = searchRange.length / 2;
				searchRange.length = index - searchRange.location;
				break;
			}
			case NSOrderedDescending:
			{
				int oldLocation = searchRange.location;
				searchRange.location = index+1;
				searchRange.length = searchRange.length - (searchRange.location - oldLocation);
				break;
			}
			case NSOrderedSame:
			{
				searchRange.length = 0;
				searchRange.location = index;
				break;
			}
		}
	}	while  (searchRange.length>0);
 
	// insert at found point
	[self insertObject:aNumber atIndex:searchRange.location];
}

You should always perform a unit test. That’s basically generating test data and seeing if the result is as it was expected.

NSMutableArray *testArray = [NSMutableArray array];
 
for (int i=0; i<1000; i++)
{
	[testArray insertNumberAtSortedLocation:[NSNumber numberWithDouble:arc4random()]];
}
 
NSLog(@"%@", testArray);

You can see from the output of the NSLog that the numbers are really in the correct order. Now we used the compare: method which is built-in for NSNumbers and most other classes which can be used for values. So there is no reason why we would have to stick with NSNumber, instead we could make the method generic by replacing “NSNumber *aNumber” with “id anObject”.

That’s the cool thing about objective-C. It still works and produces the same result. So we could be so bold as to generate 1000 random dates:

NSMutableArray *testArray = [NSMutableArray array];
 
for (int i=0; i<1000; i++)
{
	[testArray insertObjectAtSortedLocation:
		[NSDate dateWithTimeIntervalSinceReferenceDate:arc4random()]];
}
 
NSLog(@"%@", testArray);

Still works. I got sorted random dates between 2001 and 2137. Our algorithm really does not care. Now for a part that is a bit harder: to sort the objects not by themselves, but by the value of a given property. Let’s say I have multiple different objects, but all of them have a property “dblValue” holding a floating point value. I could override the compare: method for all of them, or create a variant of the above algorithm to pick out a specific property and use this for the comparison.

Let’s have a test class first to be used for demonstrating it. We’ll also override the description method so that we see it’s contents on NSLogs.

TestClass.h

#import 
 
@interface TestClass : NSObject {
	double dblValue;
	NSString *title;
}
 
@property (nonatomic, assign) double dblValue;
@property (nonatomic, retain) NSString *title;
 
@end

TestClass.m

#import "TestClass.h"
 
@implementation TestClass
@synthesize dblValue, title;
 
- (NSString *) description
{
	return [NSString stringWithFormat:@"", title, dblValue];
}
 
@end

Now for the cool modification of our algorithm to use properties:

- (void)insertObject:(id)anObject atSortedLocationForKey:(NSString *)key
{
	NSUInteger count = [self count];
 
	// if there are no contents yet, simply add it
	if (!count)
	{
		[self addObject:anObject];
		return;
	}
 
	NSRange searchRange;
	searchRange.location = 0;
	searchRange.length = count;
 
	id objectValue = [anObject valueForKey:key];
 
	// bubble sort finding of insert point
	do
	{
		NSInteger index = searchRange.location + searchRange.length/2;
 
		id testObject = [self objectAtIndex:index];
		id testValue = [testObject valueForKey:key];
 
		switch ([objectValue compare:testValue])
		{
			case NSOrderedAscending:
			{
				//searchRange.length = searchRange.length / 2;
				searchRange.length = index - searchRange.location;
				break;
			}
			case NSOrderedDescending:
			{
				int oldLocation = searchRange.location;
				searchRange.location = index+1;
				searchRange.length = searchRange.length - (searchRange.location - oldLocation);
				break;
			}
			case NSOrderedSame:
			{
				searchRange.length = 0;
				searchRange.location = index;
				break;
			}
		}
	}	while  (searchRange.length>0);
 
	// insert at found point
	[self insertObject:anObject atIndex:searchRange.location];
}

If you look closely you can see that we use the valueForKey method to retrieve an object for any kind of property. It does not matter that we defined dblValue as double, we can still retrieve it this way and use it for the comparison. Again, we perform a unit test:

NSMutableArray *testArray2 = [NSMutableArray array];
 
for (int i=0; i<1000; i++)
{
	TestClass *tmpObject = [[[TestClass alloc] init] autorelease];
	tmpObject.dblValue = arc4random();
	tmpObject.title = [NSString stringWithFormat:@"%d", i];
	[testArray2 insertObject:tmpObject atSortedLocationForKey:@"dblValue"];
}
 
NSLog(@"%@", testArray2);

Still sorted nicely. If you have gotten an error about NSMutableArray not responding to this selector, then you have forgotten to add the new method to the header. 😉

Obviously this approach does not work if the sorting property is changed. In that case you still have to resort the entire array every time or invent a different approach. Potentially you could add KeyValueObserving to NSMutableArray to watch for changes of this property. The you could retain, remove, re-insert and release it.

But for those rare cases where you don’t want the performance hit of constantly resorting an array, the presented category extension works very well.

Categories: Recipes