How to Implement Insertion Sort Algorithm in Swift and Java

Insertion Sort Algorithm

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.

Full Disclosure: This post may contain affiliate links, meaning that if you click on one of the links and purchase an item, we may receive a commission (at no additional cost to you). We only hyperlink the products which we feel adds value to our audience. Financial compensation does not play a role for those products.

About Sanjeev

Sanjeev is an IT Consultant and technology enthusiast. He has more than 15 years of experience in building and maintaining enterprise applications. He is been with Android from T-Mobile G1 time but recently shifted to iOS. He loves to code and play with the latest gadgets.

Share via
Copy link