Sorting Algorithms -part 3 (Insertion Sorting)
Hi I’m Lahiru Abegunawardena. This is my 3rd article on “Sorting Algorithms” topic. You can learn about Bubble Sort and Selection sort by referring 1st and 2nd articles of this series.
Insertion sort
Today we are going to discuss about insertion sorting and how we can implement this using java. First of all we need to know that Insertion sort also follows comparison based sorting algorithm.
How does this work?
In here we divide array of elements to be sorted into two sub-lists.
- sorted: elements that are sorted (0th to selected index)
- unsorted
In this article I’m building this algorithm to sort in ascending order. So I planned to sort elements from 0th element to selected index and keep selected index to last index untouched (or you can consider them as remained unsorted).
Let’s see how this work and we will go for a better explanation
Sort using Selection sort into ascending order → 8, 5, 9, 3, 6
1. → sorted:[8], unsorted:[5, 9, 3, 6]
2. → sorted:[5, 8], unsorted:[9, 3, 6]
3. → sorted:[5, 8, 9], unsorted:[3, 6]
4. → sorted:[3, 5, 8, 9], unsorted:[6]
5. → sorted:[3, 5, 6, 8, 9], unsorted:[]
So as you can see what we do is we sort sub array from 0th index to selected index and keep the rest untouched. We continue this process until all elements are in sorted list. Let’s see how we can put this into code using java.
Implementation -Insertion.java
As you can see I used ArrayList<Integer> in order to achieve this bit easily. Lets go through the code and try to understand what I did.
In first code block I created an ArrayList arr and added items in array to it. Then I assigned size of arr to a int variable “len”.
And I went through the arr within for loop. As you can see below every round of this for loop index “i” used to represents 2 specific things.
1. new element that added to be on sorted sub-list.
2. elements from index 0 to i needed to be sorted
I created new int variable properIndex to identify proper index of this new element that we added into our sorted sub-list. Let me explain you this more.
Let’s think about the example we took before to understand insertion sort
Sort using Selection sort into ascending order → 8, 5, 9, 3, 6
1. → sorted:[8], unsorted:[5, 9, 3, 6]
2. → sorted:[5, 8], unsorted:[9, 3, 6]
3. → sorted:[5, 8, 9], unsorted:[3, 6]
4. → sorted:[3, 5, 8, 9], unsorted:[6]
5. → sorted:[3, 5, 6, 8, 9], unsorted:[]
In here line 2 look into sorted array. we can see there is a new element 5 in the sorted sub-list. But as we see this element 5 was originally in index 2 of array when we declare it, but after we sort it in that sorted sub list now it is in the index 0. So I think you can understand this more by thinking about this in al 5 lines.
So I declared this new int variable properIndex to identify this index of the new element where it should be on sorted sub-list. Then I iterate through another for loop just to identify what is the suitable index of that arr.get(i) element. So whenever I find index of the first element that is larger than our new one I assign index of that element to properIndex and break the for loop. Or else (this means i th element is the largest in sorted sub-list) keep the element where it was previously by keeping properIndex to i.
int selected = arr.remove(i);
arr.add(properIndex, selected);
in this two lines I complete the task we created by that 2nd for loop. As you can see I remove ith element from arraylist and put it to the index (properIndex) so that element can be placed where it should be. Next few code liness I added to print more illustratable output to identify how we did the sorting step by step.
So below I attached screenshot of the output of code I described here.
Performance
Let’s look what is time complexity of this.
no of items → n
Worst case → O(n²)
Worst case scenario is based on sorting descending order list into ascending order, because you have to go on both for loops completely, so I think you can understand that this is also not god for large data sets.
I hope you will find this article very helpful in learning about Insertion sort algorithm and my implementation. I would like to suggest you to try implement sorting by descending order for a better understanding on concept.
Next article will be about another sorting algorithm and its implementation or algorithm explanation. If there is anything to clarify or solve please don’t hesitate to contact me via my LinkedIn and fb page. Try all of this by yourself and if there is anything feel free to comment. Like and please Share with your friends.
