Good news everyone! Objective-C Tuesdays is back! We left off a few weeks ago talking about
techniques for inserting and removing items in arrays. Today we will cover sorting C arrays as well as
NSArray
s and
NSMutableArray
s.
Sorting C arrays with qsort()
The C standard library includes only one built-in way to sort C arrays: the
qsort()
function.
qsort()
is an implementation of the
quicksort algorithm, a good general purpose sorting algorithm.
qsort()
sorts an array in place.
The
qsort()
prototype looks like this:
qsort(void *array, size_t itemCount, size_t itemSize,
int (*comparator)(void const *, void const *));
If you're not experienced using function pointers in C, the declaration of
qsort()
will look confusing. That's because declaring a C function pointer type
is confusing. I'll use a
typedef
to make things easier to understand:
// alternate declaration of qsort using a typedef
:
typedef int (*Comparator)(void const *, void const *);
qsort(void *array, size_t itemCount, size_t itemSize,
Comparator comparator);
Function pointers are declared in the same way that functions are declared in C, except they have a
*
before the function name like other pointer variables do. But there's one hitch. In a function pointer declaration, the
*
is ambiguous; by default, C will assume the
*
is part of the return type of the function. So when you declare a function pointer, you need a set of parentheses around the
*
and the function name in order to clue in the compiler.
// declare a function returning a pointer to an int
int *returnAPointerToSomeInt(void);
// which is interpreted as:
// (int *)returnAPointerToSomeInt(void);
// declare a pointer to a function returning an int
int (*returnSomeInt)(void);
Now that we've cleared that up, let's look at the declaration of
qsort()
again.
typedef int (*Comparator)(void const *, void const *);
qsort(void *array, size_t itemCount, size_t itemSize,
Comparator comparator);
The first three parameters of
qsort()
specify the array to sort, the count of items in the array and the size (in bytes) of a single item. Note that the array is of type
void *
, which allows us to pass any type of C array into
qsort()
.
The last parameter is the comparator function.
typedef int (*Comparator)(void const *item1, void const *item2);
The comparator takes pointers to two items from the array and returns a negative number if
item1
belongs
before item2
, a positive number if
item1
belongs
after item2
and zero if the two items are equal (or have equivalent ordering). This style of comparator function is used in many languages for sorting. I think of the items positioned on a number line when trying to understand a comparator:
item1 <=====<< item2
<-+------+-----+------+------+->
-2 -1 0 1 2
item2 >>=====> item1
<-+------+-----+------+------+->
-2 -1 0 1 2
When item1 belongs
before item2, the comparator function will return a negative number; when item1 belongs
after item2, the comparator returns a positive number. This relationship is the difference between item1 and item2, or
item1 - item2
.
The C standard library doesn't include many comparator functions, but they're easy to write. Here's an example of a comparator for
int
s to sort them in natural order:
int compareInts(void const *item1, void const *item2) {
int const *int1 = item1;
int const *int2 = item2;
return *int1 - *int2;
}
We create local variables
int1
and
int2
since a void pointer will automatically convert to a typed pointer in C, and we know that
qsort()
will actually be giving us pointers to
int
s. The two parameters are also
const
, so we can't modify the
int
values that the items point to (which would cause
qsort()
to go haywire). Then we can simply return the difference between the two
int
values to determine their sort order. We could do this in one line using casts and parentheses:
int compareInts(void const *item1, void const *item2) {
return *( (int const *) item1) - *( (int const *) item2);
}
Either way, now we can use our
compareInts()
function to sort an array of
int
s:
int array[6] = { 42, 17, 57, 19, 11, 5 };
qsort(array, 6, sizeof(int), compareInts);
// array now contains 5, 11, 17, 19, 42, 57
Now suppose we wanted to sort our array in reverse order? We would still use
qsort()
to do the job, but employ a different comparator function. Here is
compareIntsReversed()
:
int compareIntsReversed(void const *item1, void const *item2) {
int const *int1 = item1;
int const *int2 = item2;
return -(*int1 - *int2);
// or simply return *int2 - *int1;
}
By reversing the sign of the comparator's return value, you can reverse the order of sorting.
int array[6] = { 42, 17, 57, 19, 11, 5 };
qsort(array, 6, sizeof(int), compareIntsReversed);
// array now contains 57, 42, 19, 17, 11, 5
The
qsort()
function is very flexible. You can sort arrays of complex types as easily as arrays of
int
s. To sort an array of C strings in lexicographic order, use the
strcmp()
function from the C standard library.
char const *array[3] = { "red", "green", "blue" };
qsort(array, 3, sizeof(char const *), strcmp);
// array now contains "blue", "green", "red"
Sorting an array of
CGPoint
s, first write a comparator:
int compareCGPoints(void const *item1, void const *item2) {
struct CGPoint const *point1 = item1;
struct CGPoint const *point2 = item2;
if (point1->x < point2->x) {
return -1;
} else if (point1->x > point2->x) {
return 1;
}
if (point1->y < point2->y) {
return -1;
} else if (point1->y > point2->y) {
return 1;
}
return 0;
}
Notice that we first compare the X coordinates of the points and only check the Y coordinates if the X coordinates are equal. This is a common pattern when sorting over multiple fields in a
struct
. Here's an example of the
CGPoint
comparator in action:
struct CGPoint pointArray[4] = {
{ 4.0f, 3.0f },
{ 2.0f, 1.0f },
{ 4.0f, 1.0f },
{ 2.0f, 3.0f }
};
qsort(pointArray, 4, sizeof(struct CGPoint), compareCGPoints);
// pointArray now contains:
// { 2.0f, 1.0f }
// { 2.0f, 3.0f }
// { 4.0f, 1.0f }
// { 4.0f, 3.0f }
Other C sorting functionsFor most common sorting jobs,
qsort()
it a reasonable choice, and it's the only choice that's included in the C standard library. OS X and iOS also include a couple of other sorting functions worth mentioning:
heapsort()
and
mergesort()
, which have the same parameters as
qsort()
and are detailed on the
qsort()
man page.
heapsort()
is slower than
qsort()
but uses a limited amount of memory while sorting, whereas
qsort()
uses recursion and can potentially overflow the stack when sorting huge arrays.
mergesort()
can be significantly faster than
qsort()
when the array is mostly in sorted order already, but is significantly slower when the array is in random order.
Sorting an NSArray
Objective-C provides a number of ways to sort an
NSArray
. Because
NSArray
objects are immutable, all the sorting methods on
NSArray
return a new sorted
NSArray
object and leave the original one unchanged. The most basic sorting method is
-sortedArrayUsingFunction:context:
, which is similar to sorting a C array with
qsort()
. The full method declaration looks like this:
- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator
context:(void *)context
The first parameter is a pointer to a comparator function. As we did for
qsort()
, I'll rewrite the method declaration using a typedef for the function pointer to make it a little easier to read:
typedef NSInteger (*Comparator)(id item1, id item2, void *context);
- (NSArray *)sortedArrayUsingFunction:(Comparator)comparator
context:(void *)context
The comparator function for
NSArray
sorting has a few differences from the
qsort()
one. It returns an
NSInteger
, which is simply a
typedef
for
int
. Instead of two items of type
void const *
, it takes two items of type
id
since
NSArray
s can only hold object types. And finally, there's an extra
context
parameter, a void pointer that allows you to pass extra information to the comparator if you need to (but you can safely ignore it if you don't need it).
Let's write a comparator function that orders
NSString
s by their length.
static NSInteger compareStringsByLength(id item1, id item2, void *context) {
return [item1 length] - [item2 length];
}
Since we can send any message to a variable of type
id
, we don't even need casts or intermediate variables here. (Of course, we'll get a runtime error if we put the wrong type of objects into our array, but comparators for
qsort()
have the similar problems.)
And now let's see it in action:
NSArray *array = [NSArray arrayWithObjects:@"Florida",
@"Texas", @"Mississippi", @"Delaware", nil];
NSArray *sortedArray = [array sortedArrayUsingFunction:compareStringsByLength
context:NULL];
// sortedArray contains:
// @"Texas"
// @"Florida"
// @"Delaware"
// @"Mississippi"
Now let's use the
context
parameter to make it easy to switch between normal and reversed sort order. We can pass a pointer to any kind of data we want, so we will use a pointer to a
BOOL
, where a
YES
value means reversed and a
NO
value means normal ordering.
NSInteger compareStringsByLength(id item1, id item2, void *context) {
BOOL *reversed = context;
NSInteger order = [item1 length] - [item2 length];
if (*reversed) {
return -order;
} else {
return order;
}
}
Now we need to pass something to the
context
parameter when we call
-sortedArrayUsingFunction:context:
NSArray *array = [NSArray arrayWithObjects:@"Florida",
@"Texas", @"Mississippi", @"Delaware", nil];
BOOL reversed = YES;
NSArray *sortedArray = [array sortedArrayUsingFunction:compareStringsByLength
context:&reversed];
// sortedArray contains:
// @"Mississippi"
// @"Delaware"
// @"Florida"
// @"Texas"
Note that we use the
&
operator to pass the
address of the
reversed
variable as the context.
If you target iOS 3.2, OS X 10.6 or later, you can use the block version,
-sortedArrayUsingComparator:
. Blocks make one-off comparator functions easier to read and understand by putting the comparator definition right along side the sort method call. We can rewrite our example this way:
NSArray *array = [NSArray arrayWithObjects:@"Florida",
@"Texas", @"Mississippi", @"Delaware", nil];
BOOL reversed = YES;
NSArray *sortedArray = [array sortedArrayUsingComparator:^(id item1, id item2) {
NSInteger order = [item1 length] - [item2 length];
if (reversed) {
return -order;
} else {
return order;
}
}];
// sortedArray contains:
// @"Mississippi"
// @"Delaware"
// @"Florida"
// @"Texas"
Since a block copies the value of variables like
reversed
in the enclosing scope at the time it's created, there's no need for a second context parameter to
-sortedArrayUsingComparator:
. Blocks are really handy, but if you find yourself writing the same comparator block in multiple places in your code, you might be better off using a plain old comparator function and
-sortedArrayUsingFunction:
instead to prevent duplicate code, in keeping with the
DRY principle. (Or you might consider how to restructure your code so that sorting is defined in only one place.)
Since items in an
NSArray
are all objects, very often the items themselves have a useful comparator method. When this is the case, the
-sortedArrayUsingSelector:
method is very handy.
NSArray
s of
NSString
s are very common, as is the need to sort in a case-insensitive manner. Using
NSString
's
-caseInsensitiveCompare:
method, we can sort this way:
NSArray *tagNames = [NSArray arrayWithObjects:@"H1",
@"body", @"A", @"Head", nil];
NSArray *sortedTagNames = [tagNames sortedArrayUsingSelector:@selector(caseInsensitiveCompare:)];
// sortedTagNames contains:
// @"A"
// @"body"
// @"H1"
// @"Head"
There's one more interesting way to sort an
NSArray
: we'll look at the
-sortedArrayUsingDescriptors:
method and the NSSortDescriptor
class next week.