Insertion Sort in Swift
Difficulty: Beginner* | Easy | Normal | Challenging
This article covers the classic sorting algorithm Merge Sort, and it’s implementation in Swift.
- This is seen as a beginner topic (first year Computer Science degree fare) but is certainly not easy.
Algorithm: A process or set of rules to be followed
Big O Notation: A mathematical notation to describe the limiting behaviour of a function when an argument tends towards infinity
Insertion Sort: A sort where the first element is taken from an unsorted sublist, and inserted into the correct position in the sorted sublist
The insertion sort algorithm involves splitting our array into a sorted sublist, and an unsorted sublist (in our initial array — we aren’t doing anything clever with our input array in any way.
So initially our sorted subarray is empty () but the unsorted subarray has the whole initial array in it!
Let us follow the algorithm step-by-step — we are moving each element in turn to the right place in the sorted sublist.
The tests and function signature
A good function header to choose for our selection sort is as follows:
func func insertionSort(_ inputArray: [Int]) -> [Int]
This gives us the opportunity to run the following tests. Since I’m completing this in the Playground, I’ll need to
import XCTest and at the bottom of the code
sortingTests.defaultTestSuite.run() to run the following tests:
The time complexity
Insertion sort is considered to be an O(n²) algorithm, as it has a nested loop
Insertion sort is a relatively simple sorting algorithm. It can be used to sort, although in Swift we often use the in built
.sort() algorithm that gets the job done!
The Twitter contact:
Any questions? You can get in touch with me HERE