How to Perform an Insertion Sort in Objective-C

Submitted by matt_eaton on Sat, 11/17/2018 - 06:46 PM

Tags

Objective-C

The insertion sort algorithm is a sorting algorithm used in computer science for sorting small amounts of data. Recently, in my old Objective-C archives, I found an insertion sort implementation that I had been created but never seen the light of day on any project. To get some use out of this code and to share this implementation with anyone looking for an Objective-C insertion sort example I thought I would write a brief tutorial describing the use case for this algorithm and how it works. First, before we get started, there are a few things to keep in mind; First is that this tutorial was created as a macOS command line application in Mojave, but any recent version of Xcode or macOS should work with the sample code. Next, this tutorial does not require extensive knowledge of Objective-C, just fundamental Computer Science and general programming knowledge. Let's jump in!

Insertion Sort in Objective-C 🚀

Before I start on the tutorial, let me provide a bit of background on the insertion sort algorithm. The insertion sort algorithm is a sorting algorithm that can be implemented with very little code compared to the more complex sorting algorithms like quicksort, mergesort, and heapsort. In my opinion, the best time to use the insertion sort algorithm is when sorting small amounts of data where time is not critical. Another benefit of the insertion sort is that it can be implemented in-place during the execution path of a function. No extra helper functions or recursive methods need to be created. One major pitfall of using the insertion sort is the time complexity, clocking in at O(n^2) at the worst case. This is often enough to deter most developers from using insertion sort.

The idea behind insertion sort is to take 2 for loops and run the outer loop starting at 1 and increment it one at a time through a mutable data set. On each of these iterations then, the inner loop then checks each of the values at the mutable array's index to see if values need to be reordered. The key thing to keep in mind is that the inner loop always starts at the index of the outer loop and navigates from the outer loop index back to zero. That way on each iteration the inner loop rechecks the mutable array. This is why this sorting algorithm works well, but only in situations where the data set is small.

- (NSArray *) mutableArrayInsertionSort: (NSArray *)unsortedArray {
 
 
    // Time complexity: O(n^2).  Worst case: i*j.
    // Space complexity: O(1)  1 for sortedArray and the mutable copy never gets added to the autorelease pool.
    // Expensive routines:
    // * replaceObjectAtIndex
 
    NSMutableArray *returnArray = [unsortedArray mutableCopy];
 
    for (int i = 1; i < [unsortedArray count]; i++) {
 
        for (int j = i; j > 0; j--) {
            int jMinus = [[returnArray objectAtIndex: (j-1)] intValue];
            int jFlat = [[returnArray objectAtIndex: j] intValue];
            if (jMinus > jFlat) {
                [returnArray replaceObjectAtIndex: j withObject: @(jMinus)];
                [returnArray replaceObjectAtIndex: (j-1) withObject: @(jFlat)];
            }
        }
    }
 
    return returnArray;
}

Here is another implementation of the insertion sort algorithm but this time using more of a C based approach with an array of NSIntegers instead of NSNumbers. You will see that in this approach there is no use of replaceObjectAtIndex: or objectAtIndex:. Just altering the data set based on index like done in C.

- (void) constantArrayInsertionSort {
 
    NSInteger searchArray[10] = {4, 5, 1, -2, 44, 31, 50, 16, 9, 15};  // NSInteger = long
 
    size_t size = sizeof(searchArray) / sizeof(NSInteger);
 
 
    for (int i = 1; i < size; i++) {
 
        for (int j = i; j > 0; j--) {
            int jMinus = (int)searchArray[j-1];
            int jFlat = (int)searchArray[j];
            if (jMinus > jFlat) {
                searchArray[j] = jMinus;
                searchArray[j-1] = jFlat;
            }
        }
    }
    // Prints out: 1,4,5,9,15,16,31,44,50
    for (int e = 0; e < size; e++) {
        NSLog(@"%ld", searchArray[e]);
    }
 
}

In Summary ⌛️

In summary I hope that this tutorial provides more information on the insertion sort algorithm and how to implement it in Objective-C. These example are a bit different but provide a glimpse into how C and Objective-C would implement the same type of algorithm. Remember, the key use case of the insertion sort algorithm is with a small data sets in places where adding methods is not an option. I hope you enjoyed this tutorial and if you have any questions, comments, or concerns, please leave a comment below and I will make sure to address it as soon as I am able to. Thank you very much for reading and the code from this tutorial can be downloaded from my Github here.

Credits: Cover image designed by Freepik.

Member for

3 years 9 months

Matt Eaton

Long time mobile team lead with a love for network engineering, security, IoT, oss, writing, wireless, and mobile. Avid runner and determined health nut living in the greater Chicagoland area.

Twitter

Github