CODEWITHSUNDEEP
objective-ccocoa-touchsorting
nik
nik

Reputation: 445

Is there any built in method for sorting in Objective-c?

I have two sorted NSMutableArrays (or I can use any other collection, not critical), I need to insert objects from the first array to the second and preserve sort order in the second array. What is the optimal (fastest) method to do that? I can implement all the known good algorithms, but my question is, if there is already some built-in method? If not, what is the best algorithm in my case?

Upvotes: 0

Views: 276

Answers (5)

JeremyP
JeremyP

Reputation: 86661

I would start by simply adding all of the objects of the first array to the second and then resorting the second. Time how long it takes. If it is acceptable, stop there.

If not, you could try a binary search to find the insertion point in the second array for each item in the first array. Since both arrays are sorted, you might be able to optimise the search by using the last insertion point as the lower bound each time round. Something like this:

NSInteger insertionPoint = -1;
for (id object in array1)
{
    insertionPoint = [self binarySearch: array2 for: object lowerBound: insertionPoint + 1];
    [array2 insertObject: object atIndex: insertionPoint];
}

Upvotes: 2

David Rönnqvist
David Rönnqvist

Reputation: 56635

The real answer would be: it depends, since you are asking: what is the fastest way of inserting objects from one array into another while preserving sort order.

There is no built in way of inserting in the right place of a sorted array. You can achieve the same effect by just adding the two arrays together but it won't be "the fastest way".

What is actually faster depends on many things like: how much data does the arrays contain, what is the ratio of data in array1 vs array2 (does one array contain much more data than the other)?, etc.

NOTE: You should probably begin with the simple solution and only optimize once you experience performance problems. Do measurements with a large data set though, to see that your solution works with whatever data your users may have.

Inserting items from one sorted array into another sorted array

If you want to merge the two arrays by inserting objects in the right place then normal algorithms apply. You should insert the smaller array into the bigger array and try to insert entire sorted sequences where possible instead of every item one by one.

For best performance you should try to make a batch insert using insertObjects:atIndexes: instead of inserting the object one by one.

You can use indexOfObject:inSortedRange:options:usingComparator: to find the index that each item should be inserted in the other array if you specify NSBinarySearchingInsertionIndex for the options. Also, the comparator you are using must be the same as the comparator that sorted the array, otherwise the result is "undefined".

With this in mind you would do something like this

Create mutable index
For every ITEM in SMALLER ARRAY
    Find the index where to insert ITEM in LONGER ARRAY
    Add (the insertion location + the location in the short array) as the index in the mutable set.
Next item.

Batch insert all items.

The documentation for insertObjects:atIndexes: tells you that "the corresponding location specified in indexes after earlier insertions have been made." Which in your case with two sorted array mean all items with a lower index will already have been added and thus you should add the index of the object in the short array to the value returned from indexOfObject:inSortedRange:options:usingComparator:.

Another (probably very premature optimization) you can do is decrease the sortedRange for every item in the loop so that you don't have to search through parts of the array that you know the item to be inserted is bigger than.

There are probably many other optimizations that can be made. You should still measure first! Hopefully this will get you started.

Upvotes: 3

mistahenry
mistahenry

Reputation: 8744

Look at the documentation here to see if any of the NSArray sort methods work for you. http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html. You can scroll down to the methods and there's 7 built-in ones for sorting. You could probably just combine the two arrays and run the sortedArrayUsingComparator: or one of the other methods.

Upvotes: 0

Shehzad Bilal
Shehzad Bilal

Reputation: 2523

NSArray *newArray=[firstArray arrayByAddingObjectsFromArray:secondArray];
newArray = [newArray sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];

Upvotes: 2

Monolo
Monolo

Reputation: 18253

The Cocoa class NSSortDescriptor together with sortedArrayUsingDescriptors: from NSArray should do what you are after.

Since you are using mutable arrays, you might want to use sortUsingDescriptors: which sorts the mutable array without creating a new one.

Upvotes: 1

Related Questions