0
\$\begingroup\$

This is quite plain vanilla, but I'm hoping for Objective-C specific feedback. Also I'd be interested in what folks think about sorting in Objective-C vs. doing all sorting in C or C++ (and which?) even in an app.

- (NSMutableArray *) quickSort: (NSMutableArray *)toSort{

    for(NSNumber *arrayMember in toSort){
        if(![arrayMember respondsToSelector:@selector(doubleValue)]){
                NSLog(@"incorrect types in input array, returning nil");
                return nil;
            }
    }

    int intLength = toSort.count;
    if (intLength == 0){
        return toSort;
    }
    else if (intLength == 1){
        return toSort;
    }else if (intLength==2){
        if ([toSort[0] doubleValue] <= [toSort[1] doubleValue]) {
            return toSort;
    }else{
        NSNumber *temp = [toSort objectAtIndex:0];
        [toSort replaceObjectAtIndex:0 withObject:[toSort objectAtIndex:1]];
        [toSort replaceObjectAtIndex:1 withObject:temp];
        return toSort;
        }
    }

    int r = arc4random_uniform(intLength);
    double pivot = [[toSort objectAtIndex:r] doubleValue];

    NSMutableArray *lowArray = [NSMutableArray array];
    NSMutableArray *highArray = [NSMutableArray array];
    NSMutableArray *equalArray = [NSMutableArray array];
    for(int i = 0; i < intLength; i++){
        double arrayMember = [[toSort objectAtIndex:i] doubleValue];
        if (arrayMember < pivot) {
            [lowArray addObject:[NSNumber numberWithDouble:arrayMember]];
        }else if (arrayMember > pivot){
            [highArray addObject:[NSNumber numberWithDouble:arrayMember]];
        }else{
            [equalArray addObject:[NSNumber numberWithDouble:arrayMember]];
        }
    }

    NSMutableArray *returnLeft = [self quickSort:lowArray];
    NSMutableArray *returnRight = [self quickSort:highArray];

    NSMutableArray *returnArray = returnLeft;
    [returnArray addObjectsFromArray:equalArray];
    [returnArray addObjectsFromArray:returnRight];

    return returnArray;

}

This function is written to sort NSNumbers formed from doubles. Here's a sample call:

NSNumber *number3 = [NSNumber numberWithDouble:92.3];
NSNumber *number1 = [NSNumber numberWithDouble:2.3];
NSNumber *number2 = [NSNumber numberWithDouble:4.3];
NSNumber *number5 = [NSNumber numberWithDouble:5.3];
NSNumber *number4 = [NSNumber numberWithDouble:-5.3];

NSMutableArray *toSort = @[number1, number2, number3, number4, number5];
NSMutableArray *sorted = [self quickSort:toSort];
NSLog(@"here's sorted array: %@", sorted);
\$\endgroup\$
  • 1
    \$\begingroup\$ If you are using a NSMutableArray, then why wouldn't you just use the built-in - sortUsingComparator: method? \$\endgroup\$ – JS1 Jul 20 '15 at 23:09
  • \$\begingroup\$ @JS1 I don't entirely know why except I noticed a job listing where people had to do more CS-y type things, like sorts, in Objective C so I wanted to see if there was something special 'besides' the direct sort SDK. But maybe it doesn't make sense... \$\endgroup\$ – sunny Jul 21 '15 at 0:06
  • \$\begingroup\$ @JS1 The sorting algorithm that sortUsingComparator: uses is undocumented. And it's implementation details are subject to change without notice. It may or may not be a quick sort. And while I'm no sorting expert, I believe that different sort algorithms are more efficient in different scenarios. \$\endgroup\$ – nhgrif Jul 21 '15 at 19:44
2
\$\begingroup\$

Starting with Xcode 4.5 (and Clang 3.3), you can use an Objective-C literal to access an item in an NSMutableArray rather than [myArray objectAtIndex:index].

For example, if I had an NSMutableArray of NSStrings, I could do this:

NSString *firstItem = myArray[0];

You can also use firstObject as well, rather than myArray[0], like this:

NSString *firstItem = [myArray firstObject];

The spacing around your braces is also odd as well. For example, I'd recommend that this:

    ...
}else{
    ...
}

Be expanded to something like this

    ...
}
else {
    ...
}

This entire section:

if (intLength == 0){
    return toSort;
}
else if (intLength == 1){
    return toSort;
}else if (intLength==2){
    if (toSort[0] <= toSort[1]) {
        return toSort;
}else{
    NSNumber *temp = [toSort objectAtIndex:0];
    [toSort replaceObjectAtIndex:0 withObject:[toSort objectAtIndex:1]];
    [toSort replaceObjectAtIndex:1 withObject:temp];
    return toSort;
    }
}

Can be simplified down to this. This does fix the strange indentation and whitespace issues as well.

if (intLength == 0 || intLength == 1) {
    return toSort;
}
else if (intLength == 2 && toSort[0] <= toSort[1]) {
    return toSort;
}
NSNumber *temp = [toSort objectAtIndex:0];
[toSort replaceObjectAtIndex:0 withObject:[toSort objectAtIndex:1]];
[toSort replaceObjectAtIndex:1 withObject:temp];
return toSort;
\$\endgroup\$
4
\$\begingroup\$
- (NSMutableArray *) quickSort: (NSMutableArray *)toSort{
    for(NSNumber *arrayMember in toSort){
        if(![arrayMember respondsToSelector:@selector(doubleValue)]){
                NSLog(@"incorrect types in input array, returning nil");
                return nil;
            }
    }

    /* stuff */
}

There is a lot to comment on in just this part of your code, so that's where my focus will lie.


First of all, given that we're working with a mutable array, we should simply sort it in place--and we should make the method a category of NSMutableArray itself.

@interface NSMutableArray(QuickSort)

- (void)quickSort;

@end

So it can be used as such:

NSMutableArray *myArray = /* array instantiation */

[myArray quickSort];

I'd make a similar category for the immutable NSArray class which returns the sorted array:

@interface NSArray(QuickSort)

- (NSArray *)quickSortedArray;

@end

And that'd be used as such:

NSArray *unsorted = /* array instantiation */

NSArray *sorted = [unsorted quickSortedArray];

This makes our method signature make more sense. Of course, NSMutableArray is a subclass of NSArray, so we can always apply the quickSortedArray method to an NSMutableArray as well, while the first recommendation (the simple quickSort method) simply sorts it in place and returns nothing.


So, that cleans up our method signature. It makes it nice, and closer to what we'd expect to see with normal Objective-C methods.

But we've got a bigger problem.

Without documenting it, your method only works for objects which responds to the doubleValue selector, and inexplicably returns nil if anything else exists in the method.

Moreover, it can only sort the array in a single direction: ascending.

Rather than the zero argument quickSort or quickSortedArray methods I recommended, what we actually need is to accept some argument that tells us by what logic to sort the array.

We need a NSComparator argument. This is what NSComparator is:

typedef NSComparisonResult (^NSComparator)(id obj1, id obj2);

In plain English, NSComparator is a block which takes two arguments (of any object type) and returns an NSComparisonResult (which describes how these two objects should be sorted).

So we want our quickSort method to take one of these and use this for the logic to sort the array. Let the caller specify how they should be sorted.

So, if as a caller of the quickSort method, I know my array contains only NSNumber objects, I can pass a comparator that treats the two inputs as strictly NSNumber, and it doesn't impact your implementation of the sorting logic.

\$\endgroup\$
  • \$\begingroup\$ As an addendum, I highly recommend writing an accurate unit test for your sorting algorithm now that you understand the problems that can result from coincidences... \$\endgroup\$ – nhgrif Jul 21 '15 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.