Sorting arrays is one of the most common operations a Java beginner should know how to do. Although arrays aren't always the most convenient way to arrange data and this applies mostly to small numbers, the concept behind array sorting has tons of applications in complex software and data science.
In this post, we will take a closer look at what insertion sort is. We included some examples and practice problems to help you fully get the hang of this concept.

## What Is Insertion Sort?

Basically, insertion sort is an algorithm developers use to organize strings of small numbers. It divides all values into two stacks - a sorted one and an unsorted one. One by one, the numbers in the “unsorted” stack are picked out and put in the right order.Let’s take a closer look at the input and the output of insertion sort:- Input: an array A with unsorted numeric elements: A[0,1, n, n-2...].
- Output: an array containing the same numbers but fully sorted. This one is typically referred to as B: B[0]B[1]...B[n-1].

- Numerical sorting (increasing order): [1, 2, 3, 4, 5]
- Numerical sorting (decreasing order): [5, 4, 3, 2, 1]
- Alphabetical sorting: [a, b, c, d]

## Understanding The Theory of Insertion Sort

Before exploring the code behind insertion sort, let’s break the algorithm down using non-technical language. Because we will be showing the code for sorting in ascending order, it makes sense to explain the algorithm step by step in this post. Step 1. Iterating between`arr[1]`

and `arr[n]`

where `n`

is a numerical value typically less than 10.
Step 2. Compare the element you chose (known as the `key`

) to the previous number in the sequence using the `sort()`

method.
Step 3. If all the elements are smaller than their successors, repeat the comparison until you find a bigger value.
Step 4. Swap a bigger value one position beyond the smaller one to create an ordered sequence.
Step 5. Repeat the process until you get a sorted string of characters## Sorting primitive arrays

Since the algorithm is one of the most straightforward Java operations, even complete beginners shouldn’t have much trouble implementing it. Here’s a step-by-step guide to sorting an array### 1. Declare an array for the sorting

To start with, let’s create a string of values we will later display using Java. To use insertion sort, you need to create an array. For that, use`int[]`

```
int[] arrayA = {10, 14, 20, 30};
```

### 2. Use sort_arr to implement the algorithm

The sort_arr method is one of the most common ways to implement insertion sort. In practice, it looks like this:```
for(int i=0; i< sort_arr.length; ++i){
int j = i;
```

### 3. Create a loop and an iterator

By using a loop in the insertion sort algorithm, developers don't have to repeat the logic for every element. Although creating loops seems complex, it’s quite simple - here’s an example:```
for(int i=0; i< sort_arr.length; ++i){
```

Now that you have a functioning loop, it’s time to create an iterator that will sort all the elements in the desired order. From now on, we will refer to the iterator as "`j`

".
```
int j = i;
```

### 4. Creating a "while loop"

When it comes to insertion sort, a "while" loop is essential for a new, sorted array. To set it up for an ascending-order insertion sort, a developer needs to comply with two conditions:- The value assigned to j has to be greater than 0
- The value assigned to
`j-1`

needs to be greater than the`j`

index

`j`

index.### 5. Sorting the array

After you set up the while loop, the`j`

and `j-1`

values will be swapped until one or both of the conditions in the while loop fail. Similarly, the sorting will be repeated for every value in the for loop until the for-loop conditions fail as well.
Here’s how the process of insertion sort works in practice:
```
int key = sort_arr[j];
sort_arr[j] = sort_arr[j-1];
sort_arr[j-1] = key;
j = j-1;
```

## Sorting an ArrayList

Although understanding the math behind insertion sort is important, when it comes to real-life software development, you will be sorting ArrayLists much more than sequences in primitive arrays. Here’s a step-by-step guide to sorting an ArrayList:- Create a new
`Element`

class for the items that belongs to the collection.`public class Element { private int id; public Element(int id) { this.id = id; }`

- Within a collection, there’s a
`compareTo()`

method - we will use this to compare the ids of two elements.`public int compareTo(Element element) { int res = 0; if (this.id < element.getId()) { res = -1; } if (this.id > element.getId()) { res = 1; } return res; } }`

- Apply the algorithm and create some loops to sort the objects in an
`ArrayList`

instead of comparing them.`public static void insertionSortArrayList(List<element> list) { for (int j = 1; j < list.size(); j++) { Element current = list.get(j); int i = j-1; while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) { list.set(i+1, list.get(i)); i--; } list.set(i+1, current); } }`

- You can add more elements to the
`ArrayList`

as well, as shown below:`List<element> list = new ArrayList<>(); // Create elements w/ IDs 0-24 for (int i = 0; i < 25; i++) { list.add(new Element(i)); } // To use insertion sort, shuffle the values Collections.shuffle(list);`

- Now it’s time for sorting:
`// This helps print values before sorting list.forEach(e -> System.out.print(e.getId() + ", ")); // Sort the list insertionSortArrayList(list); System.out.println(); // Display a sorted array list.forEach(e -> System.out.print(e.getId() + ", "));`

- Now let’s compare the input and the output to ensure we made no mistakes. Here is the comparison of the string we used as an example.
`4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,`

GO TO FULL VERSION