Project Technical Lead
Insertion sort algorithm Java
Selection sort algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.
There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.
To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and implement them in Java.
So far, we have discussed the following sorting algorithms:
- Sorting algorithms: an introduction to data sorting,
- Bubble sort,
- Comb sort,
- Big O notation: analyzing the complexity of algorithms,
- Selection sort – sorting by selection.
Today we will look at insertion sort.
Insertion sort definition
Insertion Sort is a simple and intuitive algorithm for sorting an array or list of elements. It works similarly to the method people use to sort playing cards in their hand. They keep their received cards sorted and put each new card they receive in place to maintain its relative order.
Insertion sort vs selection, quick sort, merge sort
Insertion Sort is often used as part of more complex sorting algorithms (for example, for small subsets in Quick Sort or Merge Sort) because its performance is good for small datasets. Compared to Selection Sort, which we discussed last time, it offers a stable algorithm.
Insertion sort – how it works step by step
The algorithm starts by splitting the input vector into a sorted and unsorted part. The first element of the array is automatically considered to be sorted and the remaining elements still need to be sorted. For each element in the unsorted part (from the second to the last element of the array), that element is selected and inserted at the correct location in the sorted part of the array so that the sorted part is still ordered. This step involves comparing the selected element with the other elements in the sorted part and rearranging the elements to make room for the selected element. Reshuffling can be avoided if we choose a list data type instead of an array.
We will then show a practical example in Java code.
Insertion sort advantages
- Easy to understand and implement,
- efficient for small datasets or nearly ordered arrays,
- suitable for incoming elements that need to be continuously sorted,
- does not require additional memory for sorting,
- stable.
Insertion sort disadvantages – time complexity, intensity
- However, the time complexity is still O(n²), which makes it a slow algorithm for a large dataset.
Insertion sort time intensity
Algorithm | Method | Time complexity | Memory | Stable | ||
worst | average | best | ||||
Insertion sort definition | embedding | O(n²) | O(n²) | n | O(1) | Yes |
Insertion sort animation, visualization, gif
The visualization of the Insertion sort looks like this:
Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
You can find an animation of the algorithm on Toptal. There are 8 types of algorithms, you can also play the animation backwards.
On this page you can go through the steps of the algorithm to check the time consumption of the algorithm.
Insertion sort example and Java code implementation
We will now show a simple implementation of the Insertion sort algorithm in Java.
InsertionSort.java
package sorting;
public class InsertionSort {
private int key, j;
public void sort(int data[])
{
// Start with 2nd element, as 1st is considered to be sorted
for (int i = 1; i < data.length - 1; i++) {
System.out.println(i + ". iteration (key = " + data[i] + ")");
// Element that needs to be inserted into sorted part
key = data[i];
j = i - 1;
// Move all elements > key one position to the right
while (j >= 0 && key < data[j]) {
data[j + 1] = data[j];
j--;
}
// Insert the key in its correct spot
data[j + 1] = key;
printArray(data);
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}
Main.java
import sorting.InsertionSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
InsertionSort insertionSort = new InsertionSort();
System.out.print("Input: ");
insertionSort.printArray(dataToSort);
insertionSort.sort(dataToSort);
System.out.print("Sorted: ");
insertionSort.printArray(dataToSort);
}
}
The output of this example is:
We have prepared the files with the above example in the form of code that you can run directly in Java. Download Java Insertion Sort code.
If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers.