Insertion sort in Java. Simple solution example. • IT Blog
IT Blog
Boris IT Expert

# Insertion sort in Java. Simple solution example.

Boris~November 11, 2020 /Sorting Algorithms

In this article, we will discuss the way of the implementation of the insertion sort in Java. Because the sorting algorithm is a famous question on any technical interview, I recommend to learn it. The basic idea is to divide an array list into two parts. The left side is supposed to include sorted elements. On the right side of the current elements, we have unsorted elements. We are getting the current element with each iteration and put it in the right place on the left sorted side. And repeat this procedure until an array list is a finish.

## Insertion sort of the Array List? The simple solution in Java.

Step-by-step implementation with the pictures and explanations. The most apparent solution below:

• Start the array to go through each element;
``````//Looping the array
for (int i = 0; i < array.length; i++) ``````
• Set two variables. This step is the key to the insertion sort algorithm. You need to understand the manipulation with those variables. The purpose of the first variable to get the value of the current element. We will compare that value with all elements on the left side to find the right place. The main purpose of the second variable is to point to the element after which we should insert the current element;
``````//Getting as a key current element
int current = array[i];
//Getting the element that goes BEFORE current
int j = i - 1;``````
• Start the “while” loop for comparing the current element with each element on the left. We need to stop on the element with index 0. Otherwise, you will get out of bound exception. The critical moment here is that we need to loop until the current element more than the previous one. After each iteration, we need to reduce the J index by one to move it to the next left element;
``````//Checking if previous element more or equal to zero to avoid go outside the array
//Checking if the current element less than previous element

while (j >= 0 && current < array[j]) {
//Temporary variable to save previous element value for swapping
int temporary = array[j];

//Previous element become the next (which is current)
array[j] = current;

//Current becomes a previous
array[current] = temporary;

//After elements swapped we decrease the previous element to start new compare
j--;
}``````
• As a result, our left sorted side will increase, and the right unsorted side will decrease. And finally, we will get a sorted array list;

Animation:

Full schema:

Code example:

``````private void insertionSort() {
//Creating array of integers
int[] array = {4,2,3,1,5};

//Looping the array
for (int i = 0; i < array.length; i++) {
//Getting as a key current element
int current = array[i];
//Getting the element that goes BEFORE current
int j = i - 1;

//Checking if previous element more or equal to zero to avoid go outside the array
//Checking if the current element less than previous element

while (j >= 0 && current < array[j]) {
//Temporary variable to save previous element value for swapping
int temporary = array[j];
//Previous element become the next (which is current)
array[j] = current;
//Current becomes a previous
array[current] = temporary;
//After elements swapped we decrease the previous element to start new compare
j--;
}
}

for (int i : array) {
Log.d("arrayList", "-> " + i);
}
}``````

In this article, you see an example of the insertion sort in Java.

Full code and more examples in my facebook group.

Useful links: