In this article, we will learn about the sorting algorithm, specifically the Insertion sort Java algorithm. We will look at what Insertion sort is and how does it work. We will discuss when this performs the best and when it performs the worst and will also look into the time and space complexity of it.
1. Introduction
Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.
The importance of sorting lies in the fact that data searching can be optimised to a very high-level if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats.
Insertion Sort is one of the sorting algorithms. It works the way we sort playing cards in our hands.
2. In-place Sorting and Not-in-place Sorting
Sorting algorithms may require some extra space for comparison and temporary storage of a few data elements. The algorithms that do not require any extra space is said to happen in-place. Bubble sort is an example of in-place sorting. However, in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted. Sorting which uses equal or more space is called not-in-place sorting. Merge-sort is an example of not-in-place sorting.
2.1 Algorithm
In this section, we will look at how the algorithm for the Insertion sort works. Below is the simplistic view of the algorithm.
- If it is the first element, it is already sorted. return 1;
- Pick next element
- Compare with all elements in the sorted sub-list
- Shift all the elements in the sorted sub-list that is greater than the value to be sorted
- Insert the value
- Repeat until the list is sorted
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]
Let say we have a method that takes an array of the elements which we need to sort and the size. We will loop from the second (array indexes starts from 0 that’s why we are looping from 1) element till the last. In every iteration, we will pick the element and will insert it in the right place.
3. Insertion Sort Java Example
In this section, we will see how the Insertion sort works using an example. Let’s say we want to sort a list of numbers as shown below.
32, 19, 41, 9, 15
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
i = 1. Since 19 is smaller than 32, move 32 and insert 19 before 32
19, 32, 41, 9, 15
i = 2. 41 will remain at its position as all elements in A[0..I-1] are smaller than 41
19, 32, 41, 9, 15
i = 3. 9 will move to the beginning and all other elements from 32 to 41 will move one position ahead of their current position.
9, 19, 32, 41, 15
i = 4. 15 will move to a position after 9, and elements from 19 to 41 will move one position ahead of their current position.
9, 15, 19, 32, 41
Now we have a sorted array.
4. Java Code
In this section, we will see the Java implementation of the insertion sort.
InsertionSortExample.java
import java.util.Arrays;
import static java.lang.String.format;
public class InsertionSortExample {
public static void main(String[] args) {
int arr[] = { 32, 19, 41, 9, 15 };
System.out.println(format("Input Array: %s\n", Arrays.toString(arr)));
sort(arr);
System.out.println(format("\nSorted Array: %s\n", Arrays.toString(arr)));
}
private static void sort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int value = arr[i];
int j = i - 1;
// Move elements that are greater than key, to one position ahead of their current position.
while (j >= 0 && arr[j] > value) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = value;
System.out.println(format("Iteration: %s, Output: %s", i, Arrays.toString(arr)));
}
}
}
Output: [9, 15, 19, 32, 41]
5. Time and Space Complexity
Sometimes, there is more than one way to solve the problem. We need to learn how to compare the performance of different algorithms and choose the best one to solve a particular problem. While analysing an algorithm, we mostly consider time complexity and space complexity. The Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Similarly, the Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
5.1 Comparison
In this section, we will compare the space and time complexities of most popular sorting algorithms.
| Algorithm | Time Complexity | Space Complexity |
| Quick Sort | Best: Ω(nlog(n)) Avg: Θ(nlog(n)) Worst: O(n^2) | Worst: O(log(n)) |
| Merge Sort | Best: Ω(nlog(n)) Avg: Θ(nlog(n)) Worst: O(nlog(n)) | Worst: O(n) |
| Heap Sort | Best: Ω(nlog(n)) Avg: Θ(nlog(n)) Worst: O(nlog(n)) | Worst: O(1) |
| Bubble Sort | Best: Ω(n) Avg: Θ(n^2) Worst: O(n^2) | Worst: O(1) |
| Insertion Sort | Best: Ω(n) Avg: Θ(n^2) Worst: O(n^2) | Worst: O(1) |
As we can see that the Insertion sort is not that good if the list of elements which we are sorting is large. For a large data set, it is better to use Quick, Merge or Heap sort. Insertion sort performs best of the list is small. One good thing about insertion sort is that it’s quite simple to implement and understand and it does not need extra space for sorting.
6. Conclusion
In this article, we discussed sorting, in particular, Insertion Sort. We discussed how the insertion sort works and what is it’s time and space complexity. We compared the time and space complexity with other commonly used sorting algorithms. We also discussed the Java implementation of the sorting algorithm.
7. Download the Source Code
This was an example of Insertion Sort.
You can download the full source code of this example here: Insertion Sort Java Example
