Insertion Sort in Java

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].

There are a handful of ways to use insertion sorting - here are the most popular:

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

Note: if you have an empty array or a singleton, these are considered to be sorted by default.

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

As soon as both conditions in the while loop are true, the array's key value will equal the 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:

1. 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;
       }
   

2. 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;
       }
   }
   

3. 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);
       }
   }
   

4. 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);
   

5. 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() + ", "));
   

6. 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,
   

Insertion Sort Practice Problems

Now that you have the hang of this sorting algorithm, it’s time to put your theoretical and practical skills to the test. Theory quiz #1 You are given an array [1, 4, 6, 8] and are adding a new element n = 7 to it. What is the number of comparisons will you need to make to get a sorted sequence of numbers? Indicate the final value of index n in the array. Theory quiz #2 At a job interview, a team lead asks you to prove that sort insertion is an inefficient method. Given a numeral string of [0, 3, 6, 8, 9], what should the order of your input sequence be to maximize the running time required for sorting? Practice problem Sort the [0, 1, 4, 5, 2, 3, 7, 9, 8] array in its ascending order using insertion sort for Java.

Conclusion

The biggest challenge in grasping insertion sort is in understanding how the process works. Once you have the hang of it, turning the template into code is a piece of cake. As long as you practice and revisit relevant practice problems over time, you will rapidly improve your insertion sort speed.