1. Overview
Insertion Sort is a comparison-based sorting algorithm that gradually builds the final sorted array by moving one element at a time. It divides the array into two sections: the sorted portion (on the left) and the unsorted portion (on the right). In this article, we will delve into the implementation of Insertion Sort in Java.
Additionally, we will explore Shell Sort, an extension of the Insertion Sort algorithm. Shell Sort is designed to improve upon the performance of Insertion Sort in certain scenarios. By understanding both algorithms, you’ll gain insights into how to improve sorting efficiency for different types of data.
Please note that while we implement these algorithms in Java, their logic is language-independent. You can apply the same concepts to implement them in the programming language of your choice.
1.1 The Arrays class
Interestingly, Java’s standard library (java.util.Arrays
class) includes the Insertion Sort algorithm. However, it is essential to note that the Java library provides various sorting algorithms, each tailored for different scenarios. Some of these sorting algorithms are:
- Merge Sort: Known for its stable and efficient performance on a wide range of data sets. It is often the default choice for objects and arrays of objects.
- Counting Sort: An excellent option for sorting non-negative integer arrays when the range of values is relatively small.
- Binary Sort: A simple sorting algorithm that works efficiently for small arrays or partially sorted data.
- Heap Sort: Offers a comparison-based sorting mechanism using a binary heap data structure. It provides an optimal worst-case time complexity of O(n log n).
- Tim Sort: A hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It performs well on various data sets, especially when data contains natural runs.
Java automatically chooses the appropriate sorting algorithm based on factors such as the array’s size, data type, and other considerations. For instance, for small primitive arrays with less than 44 elements, Java uses Insertion Sort due to its simplicity and efficiency for such cases. However, for larger primitive arrays with 44 elements or more, the algorithm of choice depends on the specific size and data type of the array.
2. Time & Space Complexity
Insertion Sort has a space complexity of O(1) in Big O notation, meaning it operates in place and does not require any additional memory beyond the original array. The algorithm only uses one variable to hold the current element during the sorting process.
Regarding time complexity, in the worst-case scenario, Insertion Sort has a quadratic time complexity of O(n^2), where ‘n’ represents the number of elements in the array. This occurs when the array is in reverse order, and each element needs to be compared and shifted through the sorted portion of the array.
However, the best-case scenario occurs when the array is already sorted or nearly sorted. In such cases, Insertion Sort’s time complexity improves significantly to O(n). This is because, in the best-case scenario, the algorithm requires only one comparison for each element to find its correct position in the sorted array.
3. How Insertion Sort Works
Insertion Sort works by dividing the array into two portions: the sorted portion and the unsorted portion. The sorted portion initially contains the first element of the array, as a single element is considered sorted. The remaining elements in the array are part of the unsorted portion. Even though it may be already sorted.
To illustrate the sorting process, let’s consider the following array as an example: {-7, 2, -5, 4, -3, -1, 8, 6, -9, 0}
. In order to sort this array using Insertion Sort, the following steps are performed. Please note that while the provided code can be further optimized, it prioritizes readability over optimization.
- Start by defining a loop pointer
i
, to traverse the array starting at index 1 whilei
is less than the arraylength
.- Within each iteration of the loop, assign the value at the current index,
i
, to a variable calledcurrentValue
. - Set
ptr
toi - 1
initiating a backwards loop.- Within the backwards loop, compare the value at
array[ptr]
withcurrentValue
whileptr
is greater than or equal to 0. Ifarray[ptr]
is greater thancurrentValue
, shift the value atptr
toptr + 1
, one position to the right. - Continue this process until
ptr
becomes less than 0 orarray[ptr]
is no longer greater thancurrentValue
.
- Within the backwards loop, compare the value at
- Within each iteration of the loop, assign the value at the current index,
- Finally, after breaking out of the backwards loop, place
currentValue
atarray[ptr + 1]
. This step ensures thatcurrentValue
is inserted into the correct position within the sorted portion. Keep in mind it may be the exact same position it was originally copied from.
The video below demonstrates how Insertion Sort works and while it does not provide an exact representation of how the values shift, as they are copied rather than moved, we chose to include moving visuals for educational purposes.
3.1 Insertion Sort Implementation
To implement Insertion Sort in Java, we’ll start by creating a class called InsertionSort
. Inside this class, we will add a public static method sort(int[] array)
that takes an array of primitive integers and sorts it using the Insertion Sort algorithm.
Here’s the initial implementation of the sort()
method:
package com.youlearncode.algorithms; public class InsertionSort { // Note that we opted for static so there is no need to create an object. public static void sort(int[] array) { // Checks for null references. We chose to throw an Exception. Feel free to modify it as you see fit. if (array == null) throw new IllegalArgumentException("Input Array cannot be null!"); int length = array. Length; // Note that if the array length is 1 or 0, then it is sorted. if (length <= 1) return; // For Insertion Sorting, the first element is already considered sorted. // That is, there is no way to compare it to anything going backwards. So, it makes sense to start our loop at 1 instead of 0. for (int i = 1; i < length; i++) { int currentValue = array[i]; // Note that if we had initialized our previous for-loop at 0, then, the next line would've evaluated to -1 for its first iteration. int ptr = i - 1; for (; ptr >= 0 && array[ptr] > currentValue; ptr--) array[ptr + 1] = array[ptr]; // Broke out of the for-loop, copy currentValue to array[ptr + 1], so its rightly placed in the sorted portion. array[ptr + 1] = currentValue; } } // End of sort method }
In this implementation, we use a loop to iterate through the array, starting from the second element (index 1). Within each iteration, we store the current value in the variable currentValue
, and then we move backward through the sorted portion of the array to find the correct position for currentValue
. This is done by comparing currentValue
with each element in the sorted portion and shifting larger elements one position to the right until the correct position is found. Finally, we insert currentValue
into the correct position in the sorted portion.
In Chapter 3.3, we will explore how to turn the sort()
method into a generic one that can accept arrays of any type, including classes.
3.2 Further Optimizing Insertion Sort
While further optimization of this code to make it shorter is possible, it may come at the cost of added complexity and reduced readability. However, there is one minor change that can significantly reduce the number of swaps as the array grows larger. By wrapping the second for-loop inside an if-statement, we can achieve this improvement without compromising its overall simplicity.
if (currentValue < array[ptr]) { for (; ptr >= start && array[ptr] > currentValue; ptr--) array[ptr + 1] = array[ptr]; // After breaking out of the for-loop, assign currentValue to array[ptr + 1], so it's rightly placed in the sorted portion. array[ptr + 1] = currentValue; }
As you can see, this modification streamlines the code without introducing additional complexity, resulting in improved efficiency during sorting. Then, for the main method, we just need an unsorted array of integers:
public static void main(String[] args) { int[] intArray = {-7, 2, -5, 4, -3, -1, 8, 6, -9, 0}; System.out.println("Before sorting:\n" + Arrays.toString(intArray)); InsertionSort.sort(intArray); System.out.println("After sorting:\n" + Arrays.toString(intArray)); }
As a result, we get a beautifully sorted array:
Before sorting: [-7, 2, -5, 4, -3, -1, 8, 6, -9, 0] After sorting: [-9, -7, -5, -3, -1, 0, 2, 4, 6, 8]
3.3 Generalization of the Sort Method to Accommodate Array of Classes
In Java, primitives are special predefined types designated by reserved keywords. They typically offer faster performance and consume less memory. However, unlike some other languages like C#, Java does not support the use of primitives with generics. Instead, we must always use their wrapper counterparts. Consequently, a one-size-fits-all approach is not possible.
Nevertheless, we can achieve a unified solution for arrays of classes by utilizing a single method, provided that the class implements the Comparable
interface. This interface allows us to define a natural ordering for instances of the class, enabling sorting based on this defined order.
Conversely, when working with primitive arrays, we need to create overloaded versions of the sort()
method for each distinct primitive type. This involves writing separate implementations for byte
, short
, int
, long
, float
, double
, and char
to handle each primitive type independently and more efficiently.
In summary, we can create a generic sort()
method for arrays of classes that implement Comparable
, ensuring a unified sorting solution for classes. On the other hand, for primitive arrays, we need to provide specific implementations for each primitive type using overloaded methods.
3.3.1 Implementation of the Generic Insertion Sort Algorithm
Now, let’s dive into the implementation of our generic method. With a few adjustments, we can modify the method to accept any array of classes, as long as those classes implement the Comparable interface.
// Note that E extends the interface Comparable<E> and that our array is of E type. public static <E extends Comparable<E>> void sort(E[] array) { if (array == null) throw new IllegalArgumentException("Input Array cannot be null!"); int length = array.length; if (length <= 1) return; for (int i = 0; i < length; i++) { E currentValue = array[i]; int ptr = i - 1; // Note that this time we cannot use comparison operators on E. E could be just about anything. // We must call the compareTo method, which will provide the implementation for comparison. if (currentValue.compareTo(array[ptr]) > 0) { for (; ptr >= 0 && array[ptr].compareTo(currentValue) > 0; ptr--) { array[ptr + 1] = array[ptr]; } array[ptr + 1] = currentValue; } // End of if. } }
As you can see, with just minor adjustments we were able to generalize our method to accommodate any array of classes. This enhancement enables us to sort any array of classes using the algorithm. Nevertheless, it’s important to note that the choice of Insertion Sort may not be suitable for every array of classes, and it’s essential to understand that this generalization is intended for learning purposes.
Now, let’s explore the code in the main method to utilize the generic sorting method we discussed earlier. Firstly, we will need an array of a class that implements Comparable
, for instance the java.lang.String
class. Then, all we need to do is initialize an unsorted array of strings and pass it to the method, like so:
String[] strArray = {"M", "J", "F", "B", "X", "A", "G"}; System.out.println("Before sorting:\n" + Arrays.toString(strArray)); InsertionSort.sort(strArray); System.out.println("After sorting:\n" + Arrays.toString(strArray));
As a result, we get a beautifully sorted array.
Before sorting: [M, J, F, B, X, A, G] After sorting: [A, B, F, G, J, M, X]
4. How Shell Sort Works
In this chapter, we explore the Shell Sort algorithm, a variation of Insertion Sort often hailed as an improvement or optimization of the latter. With some minor adjustments, we can effortlessly transform our existing Insertion Sort algorithm into a more efficient Shell Sort algorithm.
The core of Shell Sort lies in a for-loop that rearranges the elements in the array based on a chosen gap size before applying the Insertion Sort technique. Interestingly, different implementations of Shell Sort may employ distinct gap sizes, such as Hibbard’s, Pratt’s, Sedgewick’s, and Knuth’s Gap Sequences.
If you have been following this article, you will recall that in Chapter 2 Time & Space Complexity, we mentioned that the time complexity of this algorithm could significantly improve if the array is already sorted or nearly sorted. So, let’s observe what happens when we pre-sort the array by applying the Gap Sequence.
4.1. Implementation of the Shell Sort Algorithm in Java
Let’s delve into the details of the Shell Sort algorithm and uncover the potential enhancements it brings to the sorting process.
public static void sort(int[] array) { sort(array, 0, array.length); } private static void sort(int[] array, int start, int length) { if (length <= 1) return; for (int gap = (length / 2); gap > start; gap /= 2) for (int i = start; i < length - gap; i++) if (array[i] > array[i + gap]) swap(array, i, i + gap); InsertionSort.sort(array); // Note that here we invoke sort(int[] array) method in InsertionSort class. } private static void swap(int[] arr, int firstIndex, int secondIndex) { int temp = arr[firstIndex]; arr[firstIndex] = arr[secondIndex]; arr[secondIndex] = temp; }
In the code above, if the specified condition is satisfied, we call the swap
method, which exchanges the values in the array based on the given indexes. For this illustration, we have chosen one of the simplest implementations of the Gap Sequence, which involves dividing the length of the array by two for each iteration. During the sorting process, we compare the values on the left and right sides of the gap. If the value on the left is greater than the one on the right, we perform a swap; otherwise, we increment both the index i
and the gap
by 1.
Let’s consider the array we used previously, [-7, 2, -5, 4, -3, -1, 8, 6, -9, 0]. By applying the Gap Sequence before invoking Insertion Sort, we obtain the following partially sorted array: [-9, -7, -5, -3, -1, 2, 0, 4, 6, 8]. Note that the resulting array is nearly sorted, with only the elements 2 and 0 requiring swapping.
As a result, we get a beautifully sorted array.
Before sorting: [-7, 2, -5, 4, -3, -1, 8, 6, -9, 0] After sorting: [-9, -7, -5, -3, -1, 0, 2, 4, 6, 8]
5. Comparing Insertion and Shell Sort: Performance and Swaps Analysis
To conduct a comparative analysis of both algorithms, we devised a method that generates random arrays of integers based on the provided size. Subsequently, we measure the execution time of each algorithm for sorting and count the number of swaps required. For clarity, a swap refers to every time a value is assigned, so if the swap method is called, we increment the counter by 2 to account for the two assignments performed. Finally, we present the results by printing them to the terminal.
Keep in mind that the number of swaps and execution time may vary depending on the arrangement of integers in the array. It’s important to note that Shell Sort may perform worse than Insertion Sort, especially for small arrays, depending on the sequence of elements generated. And now, let’s look at the results:
5.1 Insertion Sort Results
- 10 elements: 0.00013 seconds & 29 swaps.
- 100 elements: 0.00064 seconds & 2658 swaps.
- 1,000 elements: 0.0033 seconds & 251,881 swaps.
- 10,000 elements: 0.040 seconds & 25,136,097 swaps.
- 100,000 elements: 2.76 seconds & 2,502,925,167 swaps.
- 1,000,000 elements: 268.45 seconds & 250,034,781,850 swaps.
5.2 Shell Sort Results
- 10 elements: 0.000084 seconds & 20 swaps.
- 100 elements: 0.00020 seconds & 1001 swaps.
- 1,000 elements: 0.0031 seconds & 45,745 swaps.
- 10,000 elements: 0.0125 seconds & 4,065,155 swaps.
- 100,000 elements: 0.50 seconds & 392,951,241 swaps.
- 1,000,000 elements: 42.35 seconds & 40,341,482,991 swaps.
We attempted to sort 10 million elements, but it took way too long, so we decided to give it up because it was definitely not worth it.
6. Conclusion
As demonstrated by this article, Insertion Sort and Shell Sort may be suitable options for sorting small arrays. However, they perform poorly for large arrays and should not be used in such cases. Instead, the preferable choices for large arrays are Quicksort (including Dual Pivot Quicksort), Mergesort, and Heapsort. Check out our GitHub Page for the source code used in this article and feel free to test out the algorithm yourself.