Sorting an int array using Objective-C - Optimization

Question

This morning I came across this topic. Why is it faster to process a sorted array than an unsorted array? and found it really interesting!

I wanted to try it in Objective-C, and, implementing it, I ran into the problem of sorting an array of integers. Hence the following question.

Consider an array of integers arraySize initialized with random values ​​from 0 to 256:

 int data[arraySize]; for (int c = 0; c < arraySize; ++c) { data[c] = arc4random() % 256; } 

I would like to sort this array and store the result in another array of integers. In C ++, we could do something like:

 std::sort(data, ...); 

In Java, we will use:

 Arrays.sort(data); 

In Objective-C, I did it like this:

 int sortedData[arraySize]; NSArray* sortedArray = [NSArray array]; // Initialize the array to sort. for ( int i = 0 ; i < arraySize ; ++i ) { sortedArray = [sortedArray arrayByAddingObject:[NSNumber numberWithInt:data[i]]]; } // Sort the array. sortedArray = [sortedArray sortedArrayUsingSelector:@selector(compare:)]; // Copy the array back into a int[] array. for (int c = 0; c < arraySize; ++c) { sortedData[c] = [sortedArray[c] intValue]; } 

It works, but it seems to me that this is a real pain, and it is not optimized at all! How can I improve this?

Answer 1

The "non-optimized" statement is only valid for the code that you have. Apple frameworks are very optimized, and you should not assume that Apple guessed, they already guessed that you already guessed.

First use the methods to create them. The way to create an unsorted array simply erases the memory. In each individual step of the loop, you create a new instance of the array, in the end, you get 256 (or something like an array of the original array) arrays, which is just superfluous.

So, if you really, badly want to use Objective-C to solve this problem, you can use a mutable array, and you only need one NSMutableArray :

 int array[256]; // populate the C array here NSMutableArray *objcArray = [NSMutableArray array]; for (int i = 0; i < sizeof(array) / sizeof(*array); i++) { [objcArray addObject:[NSNumber numberWithInt:array[i]]; } [objcArray sortUsingSelector:@selector(compare:)]; 

By the way, even two loops (one for filling the C array and one for converting to NSMutableArray ) are not needed here. You can just write

 const size_t size = 256; NSMutableArray *objcArray = [NSMutableArray array]; for (int i = 0; i < size; i++) { [objcArray addObject:[NSNumber numberWithInt:arc4random_uniform(256)]; } [objcArray sortUsingSelector:@selector(compare:)]; 

However, you do not need Objective-C to sort an integer array. You can simply write a C function (or, if you want, an Objective-C method) to sort the integer array in place, and this can be somewhat more efficient or faster:

 #include <math.h> #include <stdlib.h> #include <unistd.h> int compare(const void *first, const void *second) { return *(const int *)first - *(const int *)second; } - (void)sortArray:(int *)array ofSize:(size_t)sz { qsort(array, sz, sizeof(*array), compare); } 

Then use it as follows:

 int array[256]; for (int i = 0; i < sizeof(array) / sizeof(*array); i++) { array[i] = arc4random_uniform(256); } [self sortArray:array ofSize:sizeof(array) / sizeof(*array)]; 

Also, read this about arrays . Really nice article.

Answer 2

How about using NSSortDescriptor?

 NSSortDescriptor *descriptor = [[NSSortDescriptor alloc] initWithKey:@"propertieToSort" ascending:NO]; NSArray *descArray = [NSArray arrayWithObject:dateDescriptor]; representedItems = [unsortedItems sortedArrayUsingDescriptors:descArray]; 

I am not 100% sure that this will work with non NSObjects, but I swear that I once used it.

Answer 3

You can use C ++ in the obj-c project, just rename your file to .mm and add #include <algorithm> to use std.sort. I think it will be faster to use NSNumber for int data p>