Insertion sort algorithm Java
Sorting 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.
V článku sa dozvieš:
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:
- Sorting algorithms: Introduction to data sorting
- Bubble sort
- Comb sort
- Big O notation: analysis of algorithms’ time and space complexity
- Selection sort
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
The algorithm starts by splitting the input vector into a sorted and an unsorted part. The first element of the array is automatically considered to be sorted, and the remaining elements must still be sorted. For each element in the unsorted part (from the second to the last element of the array), this element is selected and inserted at the correct position 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 reordering the elements to make room for the selected element. Reordering can be avoided if we choose a list data type instead of an array.
We will show a practical example of selection sorting in Java code later.
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
- The time complexity is still O(n²), making it a slow algorithm for a large dataset.
Insertion sort time complexity
| Algorithm | Method | Time Complexity | Memory | Stable | ||
| worst | average | best | ||||
| Insertion sort | 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
Visit Toptal for interactive visualizations. There are 8 types of algorithms and you can also play the animation backwards.
On this page you can go through the steps of the algorithm to check the time taken by the algorithm.
Insertion sort Java 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 insertion sort example is:
We have prepared the files with the above example as code that you can run directly in Java. Download the Java insertion sort code here.
If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers!
