Is it possible to easily check if an array is sorted in Objective-C? And if not, what's the "Best Practice" way to do it on my own?

Question

I know it is possible to sort an array with an NSSortDescriptor when I create the array, but is there a pre-built way to take an array that already exists and tell if it is already sorted?

If not, I can think of 2 ways I could do this myself:

The code in this question.
Creating a new array from my old array, but use a NSSortDescriptor when I make the new one, then check to see if the two arrays are equal.

My code optimization is a little rusty, so which of those 2 ways would be better (faster/most stable)? Or is there another way I could check that would be better than either of these?

Your best bet is just to re-sort it anytime you want the assurance or else have a custom collection object with a flag to include whether or not it has been sorted (which you would set yourself when you KNOW that it's sorted). — Jeremy
– Jeremy, Commented Oct 10, 2012 at 16:28

CRD · Accepted Answer · 2012-10-10 17:52:22Z

1

The question you refer to states the algorithm is O(n) and is as fast as you can get. Sorting in general is always going to be more costly than that; with some algorithms, e.g. bubble sort, taking just O(n) if and only if the input is already sorted.

So your suggestion (1) is always going to beat your suggestion (2), as the latter is the cost of the sort plus the cost of the equality test, and the equality test is O(n) by itself.

If you have a mutable array and wish to maintain whether it is sorted then set a flag when it is sorted and reset the flag on any addition.

answered Oct 10, 2012 at 17:52

CRD

53k5 gold badges73 silver badges87 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

GeneralMike Over a year ago

Thanks for the thorough explanation. I knew that sometimes built-in algorithms can be faster than coding things the simple way yourself, but it sounds like the simple way is the best in this case. I was thinking about my specific problem some more, and in the case I was looking at I'm going to be reading data from a database and putting it into my array, then it is never changed after that, so I'll just make sure I sort it when I read it in and I'll be good. You answer is still good to know for future reference when I won't have as much control over my array.

Scott Allen · Accepted Answer · 2012-10-10 19:34:53Z

-1

Another method here would be to subclass NSMutableArray, which would have a BOOL sorted property, which you would set when you sort the array.

If you don't want to subclass, you could set a key on the array, which indicates the same thing, and then it stays with the array if you pass it around.

// create array
NSMutableArray* array = [NSMutableArray arrayWithCapacity:1];
[array setValue:NO forKey:@"sorted"];

//... insert values
//... sort

// check if sorted
BOOL sorted = [array valueForKey:@"sorted"];

// add a new value to the array
[array addObject:obj];
[array setValue:NO forKey:@"sorted"];

answered Oct 10, 2012 at 19:34

Scott Allen

1,1991 gold badge12 silver badges14 bronze badges

2 Comments

Tim Over a year ago

Two major problems with this answer: Subclassing is a pretty bad idea, because NSMutableArray is a class cluster, not a concrete class. It is difficult to subclass to say the least, and it's actively discouraged in the documentation. Also, you can't do setValue:forKey: on an NSMutableArray; you're thinking of NSMutableDictionary. (While NSMutableArray does support setVale:forKey: (from NSObject) it doesn't do what you think: it instead invokes that method on all the objects in the array.)

Scott Allen Over a year ago

Researched this, and you are dead on, I was not aware of that behavior of the keyvalue protocol on the mutable array. Thanks for the correction.

Collectives™ on Stack Overflow

Is it possible to easily check if an array is sorted in Objective-C? And if not, what's the "Best Practice" way to do it on my own?

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related