Insertion Sort implements an algorithm similar to ordering a hand of cards in ascending order. The algorithm is O(n^2) execution and typically is useful when sorting a rather small number of elements.
Several years ago (November 03, 2016) I generated the post Insertion Sort in this blog. The code snippets do not look nice. It seems that the tool I was using to format source code is no longer working as expected.
In this post I will revisit the subject. Will use the Java programming language and the VSCode IDE on a Windows 11 computer.
9, 2, 7, 1, 8, 3 main <<< arr: [9, 2, 7, 1, 8, 3] main <<< sorted arr: [1, 2, 3, 7, 8, 9] 9,2,7,1,8,3,4 main <<< arr: [9, 2, 7, 1, 8, 3, 4] main <<< sorted arr: [1, 2, 3, 4, 7, 8, 9] 6 main <<< arr: [6] main <<< sorted arr: [6] 8,5 main <<< arr: [8, 5] main <<< sorted arr: [5, 8] 6,5,3,1,8,7,2,4 main <<< arr: [6, 5, 3, 1, 8, 7, 2, 4] main <<< sorted arr: [1, 2, 3, 4, 5, 6, 7, 8]
We have a set of test cases. Test cases are separated by two blank lines.
The first is the input line. It contains a list of unsorted integers.
Our test scaffold seems to read the input line and populate an int[] arr and display its contents. This is done to verify that all is well before calling the function of interest that implements the Insertion Sort algorithm.
The next and last line seems to display the sorted array.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read data and populate array ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.map( s -> s.trim() )
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** make a copy of the input array ****
int[] shuffled = arr.clone();
// **** loop a few times ****
int n = 13;
for (int i = 0; i < n; i++) {
// **** get a copy of the input array ****
arr = shuffled.clone();
// ???? ????
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** sort the elements in the array ****
insertionSort(arr);
// **** check if the elements in the array are sorted ****
boolean isSorted = isSorted(arr);
if (isSorted && i == 0)
System.out.println("main <<< sorted arr: " + Arrays.toString(arr));
else if (!isSorted) {
System.err.println("main <<< not sorted arr: " + Arrays.toString(arr));
System.exit(-1);
}
}
}
This is the code that implements our test scaffold.
The input line is read and the integer values are placed in the int[] arr array.
A copy of the array is made in the int[] shuffled which will be used to restore the int[] arr after it has been sorted.
We then enter a loop that repeats n times.
In the loop we restore the original array and call the function of interest to sort it.
The auxiliary function isSorted() is called to determine if the resulting array is or is not sorted.
/**
* Check if the elements in the array are sorted.
*/
static boolean isSorted(int[] arr) {
// **** sanity checks ****
int n = arr.length;
if (n <= 1) return true;
// **** traverse array ****
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
// **** array is sorted ****
return true;
}
The isSorted () utility function determines if the specified array is or is not sorted.
/**
* Insertion Sort
*
* Execution: O(n^2) - Space: O(1)
*/
static void insertionSort(int[] arr) {
// **** sanity checks ****
int n = arr.length;
if (n <= 1) return;
// **** sort array contents ****
for (int i = 1; i < n; i++) {
// **** key to be placed in sorted order ****
int key = arr[i];
// **** ****
int j = i - 1;
// ???? ????
// System.out.println("<<< i: " + i + " key: " + key + " j: " + j);
// **** ****
for ( ; j >= 0 && arr[j] > key; j--) {
// **** ****
arr[j + 1] = arr[j];
// // ???? ????
// System.out.println("<<< arr: " + Arrays.toString(arr));
}
// **** put key in array in sorted order ****
arr[j + 1] = key;
// ???? ????
// System.out.println("<<< arr: " + Arrays.toString(arr));
}
}
This is the implementation of the Insertion Sort in Java.
The function performs some sanity checks.
We then enter a loop which will move from the second to the last integer in the int[] arr placing the key in order.
In the loop the key value is specified and j is used to process the candidate location in which to stop after the first i – 1 locations have been compared and moved looking for the location of the key.
This is a good time to get a deck of cards, shuffle them, and serve a hand of two or more cards. Holding the cards, order them from left to right in ascending order. Pay attention to what you are doing and check it against the code. Chances are that you are following the algorithm implemented in this function.
Hope you enjoyed working on this algorithm as much as I did. The entire code for this project can be found in my GitHub repository named InsertionSort.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge, and enhance your developer / engineering toolset.
Thanks for reading this post and feel free to connect with me John Canessa on LinkedIn.
Enjoy;
John