Algorithm Insertion Sort Objective -C Swift

Insertion Sort algorithm: Swift & Objective-C implementations

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.

How Insertion Sort algorithm works?

This graph shows it works better than anything:

Insertion Sort algorithm

Insertion-sort-example (source: Wikipedia)

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.

Objective-C code:

Swift Code:

Efficiency & facts:

  • 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(n2) 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:

Algorithm sort comparison

Algorithm sort comparison (bigocheatsheet.com)

Any improvements?

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:

  • Swift code: link
  • Objective-C code: link

 

Have a nice day 🙂

 

About @marioeguiluz

iOS Freelancer, Entrepreneur and Mobile App Expert

Categories: Algorithm, Objective-C, Sort, Swift

Leave a Reply

Your email address will not be published. Required fields are marked *