Insertion Sort algorithm is one of the simple sorting algorithm. It works on building a sorted list by adding one element at a time.
There are many other sorting algorithm like QuickSort or MergeSort, which works better on the large unsorted lists, but insertion sort takes advantage on small and mostly sorted lists.
We are going to look at the algorithm and its implementation in Swift and Java.
Insertion Sort Algorithm
Here is a pseudo-code for the algorithm (Source Wikipedia):
for i ← 1 to length(A)-1
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
end for
We will start with second element and will loop through rest of the elements step by step. We always make sure that the left part of the list is sorted, so we pick an element and will put in the proper place in left part of the list.
To do so we will have inner loop to loop through the left part and finding the spot for the element. Once you find the spot, we will place the element and will repeat the process for next element.
Please check the Wikipedia article for more details on Insertion Sort.
Swift Implementation
We have declared two pointers for the list – forwardPointer and reversePointer.
forwardPointer will give us one element in each iteration and we will use reversePointer to find the correct spot for that element in already sorted left part of the list.
We will loop from the selected element place to the first element and compare it will each element to find the correct place. Once the correct place is found, we can place the selected element.
https://gist.github.com/SanjeevMohindra/9c2f470657da39556998772f7b506835
Java Implementation
Here is the Java implementation of the insertion sort. The logic is similar to what we have used in Swift implementation, you can check the walk-through of the same for details.
https://gist.github.com/SanjeevMohindra/c7dce63fd2fd5c86a2e6a2cd52f95e94
These are the implementation for Insertion Sort in Swift and Java. You can use the comment section about any questions on Insertion Sort.
