Bubble Sort in Objective-C

Question

Following is Objective-C method implementation I did for one of the most simplest sorting algorithms, Bubble Sort to sort an array of integers.

Note:- I have defined it as a static method in the SimpleAlgorithms class.

/**
 * When given jumbled or discending ordered array of integers, following bubble sort method will give you 
 * an array ordered in ascending order.
 */
+ (NSArray *) bubbleSort:(NSArray *) arrayToBeSorted {
 // As we can't swap integers in a static array, make a mutable array out of the given static array.
 NSMutableArray *muArrRaw = [[NSMutableArray alloc] initWithArray:arrayToBeSorted];
 // iterate through the array as rounds
 for (int i = 0; i < [muArrRaw count]; i++) {
 // iterate through each element of the array with the given range
 for (int j = 0; j < [muArrRaw count] - i; j++) {
 // comparison
 if (j < ([muArrRaw count] - 1) && [[muArrRaw objectAtIndex:j] intValue] > [[muArrRaw objectAtIndex:(j + 1)] intValue]) {
 int temp = [[muArrRaw objectAtIndex:j] intValue]; // taken the value to be swapped first
 // then do the swapping
 [muArrRaw replaceObjectAtIndex:j withObject:[muArrRaw objectAtIndex:(j + 1)]];
 [muArrRaw replaceObjectAtIndex:(j + 1) withObject:[NSNumber numberWithInt:temp]];
 }
 }
 }
 // return the sorted array
 return [muArrRaw mutableCopy];
}

I call this method as follows:

NSArray *array = [[NSArray alloc] initWithObjects:[NSNumber numberWithInt:5], [NSNumber numberWithInt:3], [NSNumber numberWithInt:4], [NSNumber numberWithInt:1], [NSNumber numberWithInt:2], nil];
NSArray *sortedArray = [SimpleAlgorithms bubbleSort:array];

I know this seems to be silly for asking for improvements for something like this. But I like to find out even smallest improvements that we can made to this kind of things also because sometimes I might have done something stupid in the above implementation also. That's where we can embed power and value to the implementation.

So please give your suggestions and improvements to this Algorithm implementation.

I would be grateful if you can point out the improvements in the following areas:

• Objective-C Language oriented improvements, reasoning and suggestions
• Algorithm implementation techniques, simplifiable code lines.

• Phrancis: Please don't edit your question after answers have been offered, see What should I do when someone answers my question?
• Randika Vishman: @Phrancis Ok, agreed, from now I will use the site complying to the above guidance! :-) thanks

Answer 1

Returning a mutable copy of the temporary array makes no sense to me, perhaps you meant

return [muArrRaw copy];

to return an immutable array (as the return type of the method indicates).

---

The "proper" data type for array indices is NSUInteger, not int.

---

In

if (j < ([muArrRaw count] - 1) && [[muArrRaw objectAtIndex:j] intValue] > [[muArrRaw objectAtIndex:(j + 1)] intValue]) {

you can get rid of the extra check j < ([muArrRaw count] - 1) if the outer loop starts with i = 1.

Also [muArrRaw objectAtIndex:j] can be shortened to muArrRaw[i],

for (NSUInteger i = 1; i < [muArrRaw count]; i++) {
 for (NSUInteger j = 0; j < [muArrRaw count] - i; j++) {
 if ([muArrRaw[j] intValue] > [muArrRaw[j + 1] intValue]) {
 // ...
 }
 }
}

---

Swapping two elements in the array can be simplified by using the existing method:

[muArrRaw exchangeObjectAtIndex:j withObjectAtIndex:j+1];

---

If no elements were swapped at all in some pass then the array is already sorted and there is no need to continue:

BOOL swapped;
NSUInteger n = [muArrRaw count];
do {
 swapped = NO;
 for (NSUInteger j = 0; j + 1 < n; j++) {
 if ([muArrRaw[j] intValue] > [muArrRaw[j + 1] intValue]) {
 [muArrRaw exchangeObjectAtIndex:j withObjectAtIndex:j+1];
 swapped = YES;
 }
 }
 n--;
} while (swapped);

---

Your method is limited to arrays of integers. If you compare two array elements with

if ([muArrRaw[j] compare:muArrRaw[j+1]] == NSOrderedDescending) { ... }

instead then it applies to all element types which have a compare: method (e.g. NSNumber, NSString, NSDate ...).

Even more general, you can add a comparator argument, as suggested in this answer:

• My own method for sorting numbers in array

• Randika Vishman: Thank for the answer! I mistakenly coded it as mutableCopy instead of return [muArrRaw copy]; and also I didn't know about exchangeObjectAtIndex:withObjectAtIndex: method of NSArray, and also that swapped flag I couldn't imagine about it before. Great!

Answer 2

Thanks to contributions from Zumry Mohamed and Martin R, I learned few things about Objective-C language usage and also got a chance to improve my implementation of Bubble Sort Algorithm.

Things I learned:

1. NSArray methods
sortedArrayUsingComparator: compare: exchangeObjectAtIndex:withObjectAtIndex:

2. And an optimization to the algorithm implementation to eliminate rounds of iterations through the elements even after they are really swapped and sorted out.

So following is my improved Bubble Sort Algorithm implementation in Objective-C:

+ (NSArray *) bubbleSort:(NSArray *) arrayToBeSorted ascendingOrder:(BOOL) sortInAscendingOrder {
 // As we can't swap integers in a static array, make a mutable array out of the given static array.
 NSMutableArray *muArrRaw = [[NSMutableArray alloc] initWithArray:arrayToBeSorted];
 BOOL swapped;
 NSUInteger n = [muArrRaw count];
 // iterate through the array as rounds
 do {
 swapped = NO;
 // iterate through each element of the array with the given range
 for (NSUInteger j = 0; j + 1 < n; j++) {
 // comparison
 if (sortInAscendingOrder && [muArrRaw[j] compare:muArrRaw[j+1]] == NSOrderedDescending) {
 [muArrRaw exchangeObjectAtIndex:j withObjectAtIndex:j+1];
 swapped = YES;
 } else if (!sortInAscendingOrder && [muArrRaw[j] compare:muArrRaw[j+1]] == NSOrderedAscending) {
 [muArrRaw exchangeObjectAtIndex:j withObjectAtIndex:j+1];
 swapped = YES;
 }
 }
 } while (swapped);
 // return the sorted array
 return [muArrRaw copy];
}

Answer 3

What you have written is working well. I just compared your method vs NSArray sortedArrayUsingComparator . Please look at the benchmark result.

NSArray *numbers = @[@100, @210, @120, @200, @134, @156, @400, @500 , @450 , @475];
NSArray *yourSort = [SimpleAlgorithms bubbleSort:numbers];
NSLog(@"Your sort ..%@ ", yourSort);
//Sort using sortedArrayUsingComparator 
NSArray *comparatorSort =[numbers sortedArrayUsingComparator:^(id ob1, id ob2){
 if ([ob1 integerValue] > [ob2 integerValue]) {
 return (NSComparisonResult)NSOrderedAscending;
 }
 if ([ob1 integerValue] < [ob2 integerValue]) {
 return (NSComparisonResult)NSOrderedDescending;
 }
 return (NSComparisonResult)NSOrderedSame;
}];
NSLog(@"After sort ..%@ ", comparatorSort);

time took to sort the arrays

yourSort - 9 milli seconds

comparatorSort - 1 milli second

My suggestion is you can still improve alot your code. Cheers!

• Mathieu Guindon: Benchmark results are interesting, but they don't constitute a review all by themselves. Can you expand on what makes OP's code "good", and how it "can still improve alot"?
• Chris Schneider: Not only that, but 8ms is insigificant and this doesn't take into account the implementation of comparator. I doubt it's a bubble sort.