When one is starting to learn about algorithms, one of the first examples is **Insertion Sort** algorithm.

The classic example to introduce **Insertion Sort** algorithm is how a poker player sorts a hand of cards in increasing order: Every time he gets a new card from the deck, he compares it to the cards which are already in his hand to find its correct place in the increasing order.

This graph shows it works better than anything:

If you want to know how Insertion Sort algorithm works in detail, I recommend you to read this article: Wikipedia – Insertion Sort

Let’s see how we can implement this algorithm with Objective-C and Swift.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//Insertion Sort of an array of integers //************************************** NSMutableArray* insertionSort(NSMutableArray* unsortedArray){ if(!unsortedArray) return nil; if(unsortedArray.count<2) return unsortedArray; for (int j=1; j<unsortedArray.count; j++) { int i = j; while(i>0 && [[unsortedArray objectAtIndex:(i-1)] intValue] > [[unsortedArray objectAtIndex:i] intValue]) { [unsortedArray exchangeObjectAtIndex:i withObjectAtIndex:(i-1)]; i--; } } return unsortedArray; } |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//Helper function to exchange position in one array //From: http://stackoverflow.com/questions/24077880/swift-make-method-parameter-mutable func exchange<T>(_ data: inout [T], i:Int, j:Int) { let temp:T = data[i] data[i] = data[j] data[j] = temp } //Insertion Sort of an array of integers func insertionSort<T:Comparable>(_ unsortedArray:Array<T>)->Array<T>{ var unsortedArray = unsortedArray if(unsortedArray.count<2) { return unsortedArray } for j in 1 ..< unsortedArray.count { var i = j while i>0 && unsortedArray[i-1]>unsortedArray[i] { exchange(&unsortedArray, i: i-1, j: i) i -= 1; } } return unsortedArray; } |

- It is well known that Insertion Sort algorithm is not as efficient as Merge Sort or other divide and conquer algorithms. However, for a low number of input elements to sort, or if we need to sort elements in-place, it could be a choice.
- Between quadratic algorithms O(
*n*^{2}) like Bubble short or Selection Sort, Insertion Sort algorithm is more efficient. - It can be used to sort data as it receives it (Online)
- Insertion Sort algorithm is used as an alternative of Quick Sort when the data input is less than some limit, in which it is more efficient.

**Algorithm chart from bigocheatsheet.com:**

*Hey reader! This post only tries to give some basic idea and an easy implementation of the Insertion Sort algorithm. If you have a better approach, some fix or some clarification to make, you are welcome!!! We can improve this together*

You can make comments on the code via Gist:

Have a nice day 🙂

**Categories: **Algorithm, Objective-C, Sort, Swift

## Leave a Reply