How can I reverse a NSArray in Objective-C?

Question

I need to reverse my NSArray.

As an example:

[1,2,3,4,5] must become: [5,4,3,2,1]

What is the best way to achieve this?

Cineaste

It's also worth looking at this: http://developer.apple.com/mac/library/documentation/Cocoa/Conceptual/Collections/Articles/sortingFilteringArrays.html which tells you how to sort an array in reverse order (which is commonly what you are doing, for instance in using an array derived from NSDictionary#allKeys, and you want reverse date/alpha order to serve as grouping for UITable on iPhone, etc). – Aludel

Answer 1

There is a much easier solution, if you take advantage of the built-in reverseObjectEnumerator method on NSArray, and the allObjects method of NSEnumerator:

NSArray* reversedArray = [[startArray reverseObjectEnumerator] allObjects];

allObjects is documented as returning an array with the objects that have not yet been traversed with nextObject, in order:

This array contains all the remaining objects of the enumerator in enumerated order.

Butane

There's an answer further down here by Matt Williamson that ought to be a comment: Don't use danielpunkass's solution. I used it thinking it was a great shortcut, but now I've just spent 3 hours trying to figure out why my A* algorithm was broken. It's because it returns the wrong set! – Doriedorin

What do mean by 'wrong set'? A array that is not in reverse order? – Haileyhailfellowwellmet

I'm no longer able to reproduce that bug. It could have been my error. This is a very elegant solution. – Foucquet

The order is now guaranteed in the documentation. – Entomology

i am sure this is the good answer but it will fail for the Mutable Objects. Because NSEnumerator provide readonly object type @property (readonly, copy) NSArray<ObjectType> *allObjects; – Mysterious

Hi @AnuragSoni - I'm not sure why that would cause it to fail. None of the methods involved in my prescription involve mutating an object. Do you mean NSEnumerator can't be used at all, for some reason, on a mutable array's allObjects ? – Butane

Hi @Butane if you are doing modification with the objects in Array received in reversedArray. – Mysterious

Answer 2

For obtaining a reversed copy of an array, look at danielpunkass' solution using reverseObjectEnumerator.

For reversing a mutable array, you can add the following category to your code:

@implementation NSMutableArray (Reverse)

- (void)reverse {
    if ([self count] <= 1)
        return;
    NSUInteger i = 0;
    NSUInteger j = [self count] - 1;
    while (i < j) {
        [self exchangeObjectAtIndex:i
                  withObjectAtIndex:j];

        i++;
        j--;
    }
}

@end

Bieber

One of the bad things about Fast Enumeration is that new guys like me don't learn about cool things like reverseObjectEnumerator. Pretty neat way to do it. – Realgar

They are better than C++ iterators, but I definitely won't miss enumerators. – Doriedorin

Wht are they better then C++ iterators? – Infuse

Because C++-iterators have an even worse syntax, they are ugly. – Doriedorin

Shouldn't you copy the array before returning it? – Yingling

this first method is really returning an NSMutableArray though, no? ;) – Gundry

@Christine: Yes, but this doesn't matter because it looks like an NSArray. If the immutability has to be enforced you can do return [array copy]. – Doriedorin

There is a bug in the mutable array if [self count] is 0 since you are using unsigned integers. – Fletafletch

@Mark: Thanks! Do you see a better fix than adding an if statement? – Doriedorin

@Georg: I disagree with you on this one. If I see a method that returns an immutable object, I expect it to actually be returning an immutable object. Having it appear to return an immutable object but actual return a mutable object is a dangerous practice to get into. – Gundry

Calling a method declared in a category on NSArray on an instance of NSMutableArray, like in this case, crashes your app. – Lorrainelorrayne

@HansSjunnesson Are you sure there's a problem with my code? I've just tested it and it worked fine. – Doriedorin

The answer from @Butane is much better for immutable arrays, but this has a reasonable implementation for mutable arrays. – Kenaz

Does - (void)reverse actually work? Surely by the time you've reversed the first half of the array, the second half will revert back to the original order? i.e.: for an array with 5 items, 1->5, 2->4, 3->3, 4->2, 5->1 and everything is back where it started? – Credendum

@CaptainRedmuff: You overlooked j-- – Doriedorin

Good call. I had missed the j--. Good stuff :] – Credendum

As pointed out below [[array reverseObjectEnumerator] allObjects] is a much more concise way to use the reverse enumerator. – Creuse

@Christine: You can always just add return [array copy]. Personally, I do not think this is necessary in most cases. – Doriedorin

NSArray* reversed = [[myArray reverseObjectEnumerator] allObjects]; use this :) – Fishman

Suggesting reverseObjectEnumerator allObjects is not helpful since it does not reverse the mutable array, Even adding mutableCopy would not help since still the original array is not mutated. Apple documents that immutability should not be tested for at run time, but be assumed based on the returned type, so returning an NSMutableArray in this case is perfectly correct code. – Agc

There is a straightforward solution to this refer to @danielpunkass's answer – Curst

Well done now mark that answer as accepted to help ppl looking for answer in future, cuz no one is going to read all the comments till here right :D – Curst

Small test shows that this method is 10 to 30 times faster than mutableArray = [[[mutableArray reverseObjectEnumerator] allObjects] mutableCopy]; – Nordstrom

@Terry: The semantics are different. In one case you modify the actual array (everywhere it's used) and in the other case you make a copy. – Doriedorin

Answer 3

Some benchmarks

1. reverseObjectEnumerator allObjects

This is the fastest method:

NSArray *anArray = @[@"aa", @"ab", @"ac", @"ad", @"ae", @"af", @"ag",
        @"ah", @"ai", @"aj", @"ak", @"al", @"am", @"an", @"ao", @"ap", @"aq", @"ar", @"as", @"at",
        @"au", @"av", @"aw", @"ax", @"ay", @"az", @"ba", @"bb", @"bc", @"bd", @"bf", @"bg", @"bh",
        @"bi", @"bj", @"bk", @"bl", @"bm", @"bn", @"bo", @"bp", @"bq", @"br", @"bs", @"bt", @"bu",
        @"bv", @"bw", @"bx", @"by", @"bz", @"ca", @"cb", @"cc", @"cd", @"ce", @"cf", @"cg", @"ch",
        @"ci", @"cj", @"ck", @"cl", @"cm", @"cn", @"co", @"cp", @"cq", @"cr", @"cs", @"ct", @"cu",
        @"cv", @"cw", @"cx", @"cy", @"cz"];

NSDate *methodStart = [NSDate date];

NSArray *reversed = [[anArray reverseObjectEnumerator] allObjects];

NSDate *methodFinish = [NSDate date];
NSTimeInterval executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"executionTime = %f", executionTime);

Result: executionTime = 0.000026

2. Iterating over an reverseObjectEnumerator

This is between 1.5x and 2.5x slower:

NSDate *methodStart = [NSDate date];
NSMutableArray *array = [NSMutableArray arrayWithCapacity:[anArray count]];
NSEnumerator *enumerator = [anArray reverseObjectEnumerator];
for (id element in enumerator) {
    [array addObject:element];
}
NSDate *methodFinish = [NSDate date];
NSTimeInterval executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"executionTime = %f", executionTime);

Result: executionTime = 0.000071

3. sortedArrayUsingComparator

This is between 30x and 40x slower (no surprises here):

NSDate *methodStart = [NSDate date];
NSArray *reversed = [anArray sortedArrayUsingComparator: ^(id obj1, id obj2) {
    return [anArray indexOfObject:obj1] < [anArray indexOfObject:obj2] ? NSOrderedDescending : NSOrderedAscending;
}];

NSDate *methodFinish = [NSDate date];
NSTimeInterval executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"executionTime = %f", executionTime);

Result: executionTime = 0.001100

So [[anArray reverseObjectEnumerator] allObjects] is the clear winner when it comes to speed and ease.

Hogle

And I can imagine that it will be a lot more than 30-40x slower for larger numbers of objects. I don't know what the complexity of the sort algorithm is (best case O(n*logn)?, but it's also calling indexOfObject, which is probably O(n). With the sort, that could be O(n^2*logn) or something. Not good! – Wifehood

What about a benchmark using enumerateObjectsWithOptions:NSEnumerationReverse ? – Aphrodisia

I just did a benchmark using enumerateObjectsWithOptions:NSEnumerationReverse -- the top one completed in 0.000072 seconds, the block method in 0.000009 seconds. – Aphrodisia

Nice observation, it makes sense to me, but I think that executions times are too short to conclude that X algorithm is Y times faster than other. In order to mesure algorithm execution performance we have to take care several things, like, Is there some process that is running at same time?. For instance, perhaps when you run the first algorithm you have more cache memory available, and so on. Moreover, there is only one data set, I think we should run with several data sets (with different sizes are compositions) to conclude. – Panama

Answer 4

DasBoot has the right approach, but there are a few mistakes in his code. Here's a completely generic code snippet that will reverse any NSMutableArray in place:

/* Algorithm: swap the object N elements from the top with the object N 
 * elements from the bottom. Integer division will wrap down, leaving 
 * the middle element untouched if count is odd.
 */
for(int i = 0; i < [array count] / 2; i++) {
    int j = [array count] - i - 1;

    [array exchangeObjectAtIndex:i withObjectAtIndex:j];
}

You can wrap that in a C function, or for bonus points, use categories to add it to NSMutableArray. (In that case, 'array' would become 'self'.) You can also optimize it by assigning [array count] to a variable before the loop and using that variable, if you desire.

If you only have a regular NSArray, there's no way to reverse it in place, because NSArrays cannot be modified. But you can make a reversed copy:

NSMutableArray * copy = [NSMutableArray arrayWithCapacity:[array count]];

for(int i = 0; i < [array count]; i++) {
    [copy addObject:[array objectAtIndex:[array count] - i - 1]];
}

Or use this little trick to do it in one line:

NSArray * copy = [[array reverseObjectEnumerator] allObjects];

If you just want to loop over an array backwards, you can use a for/in loop with [array reverseObjectEnumerator], but it's likely a bit more efficient to use -enumerateObjectsWithOptions:usingBlock::

[array enumerateObjectsWithOptions:NSEnumerationReverse
                        usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    // This is your loop body. Use the object in obj here. 
    // If you need the index, it's in idx.
    // (This is the best feature of this method, IMHO.)
    // Instead of using 'continue', use 'return'.
    // Instead of using 'break', set '*stop = YES' and then 'return'.
    // Making the surrounding method/block return is tricky and probably
    // requires a '__block' variable.
    // (This is the worst feature of this method, IMHO.)
}];

(Note: Substantially updated in 2014 with five more years of Foundation experience, a new Objective-C feature or two, and a couple tips from the comments.)

Realgar

Does that work? I don't think NSMutableArray has a setObject:atIndex: method. Thanks for the suggested fix for the loop though, and using generic id instead of NSNumber. – Miserly

You're right, I caught that when I read some of the other examples. Fixed now. – Realgar

[array count] is called every time you loop. This is very costly. There's even a function which changes the positions of two objects. – Doriedorin

Answer 5

After reviewing the other's answers above and finding Matt Gallagher's discussion here

I propose this:

NSMutableArray * reverseArray = [NSMutableArray arrayWithCapacity:[myArray count]]; 

for (id element in [myArray reverseObjectEnumerator]) {
    [reverseArray addObject:element];
}

As Matt observes:

In the above case, you may wonder if -[NSArray reverseObjectEnumerator] would be run on every iteration of the loop — potentially slowing down the code. <...>

Shortly thereafter, he answers thus:

<...> The "collection" expression is only evaluated once, when the for loop begins. This is the best case, since you can safely put an expensive function in the "collection" expression without impacting upon the per-iteration performance of the loop.

Carthy

Answer 6

Georg Schölly's categories are very nice. However, for NSMutableArray, using NSUIntegers for the indices results in a crash when the array is empty. The correct code is:

@implementation NSMutableArray (Reverse)

- (void)reverse {
    NSInteger i = 0;
    NSInteger j = [self count] - 1;
    while (i < j) {
        [self exchangeObjectAtIndex:i
                  withObjectAtIndex:j];

        i++;
        j--;
    }
}

@end

Hale

Answer 7

The most efficient way to enumerate an array in reverse:

Use enumerateObjectsWithOptions:NSEnumerationReverse usingBlock. Using @JohannesFahrenkrug's benchmark above, this completed 8x quicker than [[array reverseObjectEnumerator] allObjects];:

NSDate *methodStart = [NSDate date];

[anArray enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    //
}];

NSDate *methodFinish = [NSDate date];
NSTimeInterval executionTime = [methodFinish timeIntervalSinceDate:methodStart];
NSLog(@"executionTime = %f", executionTime);

Aphrodisia

Answer 8

NSMutableArray *objMyObject = [NSMutableArray arrayWithArray:[self reverseArray:objArrayToBeReversed]];

// Function reverseArray 
-(NSArray *) reverseArray : (NSArray *) myArray {   
    return [[myArray reverseObjectEnumerator] allObjects];
}

Gibe

Answer 9

Reverse array and looping through it:

[[[startArray reverseObjectEnumerator] allObjects] enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    ...
}];

Woodworth

Answer 10

To update this, in Swift it can be done easily with:

array.reverse()

Threlkeld

Answer 11

As for me, have you considered how the array was populated in the first place? I was in the process of adding MANY objects to an array, and decided to insert each one at the beginning, pushing any existing objects up by one. Requires a mutable array, in this case.

NSMutableArray *myMutableArray = [[NSMutableArray alloc] initWithCapacity:1];
[myMutableArray insertObject:aNewObject atIndex:0];

Favourite

Answer 12

Or the Scala-way:

-(NSArray *)reverse
{
    if ( self.count < 2 )
        return self;
    else
        return [[self.tail reverse] concat:[NSArray arrayWithObject:self.head]];
}

-(id)head
{
    return self.firstObject;
}

-(NSArray *)tail
{
    if ( self.count > 1 )
        return [self subarrayWithRange:NSMakeRange(1, self.count - 1)];
    else
        return @[];
}

Underwaist

Recursion is a terrible idea on large data structures, memory-wise. – Soothsay

If it compiles with tail recursion it should not be a problem – Fionafionna

You're initializing a new array with every recursion, this seems very inefficient. – Glasgow

Answer 13

There is a easy way to do it.

    NSArray *myArray = @[@"5",@"4",@"3",@"2",@"1"];
    NSMutableArray *myNewArray = [[NSMutableArray alloc] init]; //this object is going to be your new array with inverse order.
    for(int i=0; i<[myNewArray count]; i++){
        [myNewArray insertObject:[myNewArray objectAtIndex:i] atIndex:0];
    }
    //other way to do it
    for(NSString *eachValue in myArray){
        [myNewArray insertObject:eachValue atIndex:0];
    }

    //in both cases your new array will look like this
    NSLog(@"myNewArray: %@", myNewArray);
    //[@"1",@"2",@"3",@"4",@"5"]

I hope this helps.

Carding

Answer 14

I don't know of any built in method. But, coding by hand is not too difficult. Assuming the elements of the array you are dealing with are NSNumber objects of integer type, and 'arr' is the NSMutableArray that you want to reverse.

int n = [arr count];
for (int i=0; i<n/2; ++i) {
  id c  = [[arr objectAtIndex:i] retain];
  [arr replaceObjectAtIndex:i withObject:[arr objectAtIndex:n-i-1]];
  [arr replaceObjectAtIndex:n-i-1 withObject:c];
}

Since you start with a NSArray then you have to create the mutable array first with the contents of the original NSArray ('origArray').

NSMutableArray * arr = [[NSMutableArray alloc] init];
[arr setArray:origArray];

Edit: Fixed n -> n/2 in the loop count and changed NSNumber to the more generic id due to the suggestions in Brent's answer.

Miserly

Isn't this missing a release on c? – Binominal

Answer 15

Try this:

for (int i = 0; i < [arr count]; i++)
{
    NSString *str1 = [arr objectAtIndex:[arr count]-1];
    [arr insertObject:str1 atIndex:i];
    [arr removeObjectAtIndex:[arr count]-1];
}

Quinones

Answer 16

If all you want to do is iterate in reverse, try this:

// iterate backwards
nextIndex = (currentIndex == 0) ? [myArray count] - 1 : (currentIndex - 1) % [myArray count];

You can do the [myArrayCount] once and save it to a local variable (I think its expensive), but I’m also guessing that the compiler will pretty much do the same thing with the code as written above.

Gariepy

Answer 17

Swift 3 syntax :

let reversedArray = array.reversed()

Karisa

Answer 18

Here is a nice macro that will work for either NSMutableArray OR NSArray:

#define reverseArray(__theArray) {\
    if ([__theArray isKindOfClass:[NSMutableArray class]]) {\
        if ([(NSMutableArray *)__theArray count] > 1) {\
            NSUInteger i = 0;\
            NSUInteger j = [(NSMutableArray *)__theArray count]-1;\
            while (i < j) {\
                [(NSMutableArray *)__theArray exchangeObjectAtIndex:i\
                                                withObjectAtIndex:j];\
                i++;\
                j--;\
            }\
        }\
    } else if ([__theArray isKindOfClass:[NSArray class]]) {\
        __theArray = [[NSArray alloc] initWithArray:[[(NSArray *)__theArray reverseObjectEnumerator] allObjects]];\
    }\
}

---

To use just call: reverseArray(myArray);

Cagliostro