[Insertion Sort Advanced Analysis on Hacker Rank](https://www.hackerrank.com/challenges/insertion-sort/problem) ## Problem Description In short, the problem is about to tell how many swaps will you need to sort an array using insertion sort. So, why is this problem relevant at all ? In the end if I want to sort using this algorithm i could do it, and after that the amount of swaps wouldn't matter to much. But counting the amount of swaps could have practical benefits in data analysis or algorithm optimization, and it could be very useful if the cost of the swap if high, either in memory or in resources. That being said, let's jump to the resolution path. ## Insertion Sort First, let’s remember briefly what insertion sort is about. This sorting algorithm iterates over the array, and in each *i* iteration it will ensure that the first *i* elements of the array are in correct order. In every iteration you will look at the _i + 1_ element an will _insert_ it in the correct position of the [0, i + 1] sub-array. Providing that the first _i_ elements are sorted, when you look at the element _i + 1_, there are two possible scenarios, 1. either the element _i + 1_ is greater or equal than the element **i**, in which case you can ensure that the _i + 1_ elements are ordered (and you can continue looking at the next element), or 2. the element _i + 1_ is lower than the **i** element. In this case you will have to swap this element back until it is greater or equal than all the previous elements, at this moment the _i + 1_ array is again an ordered array. For example, if we attempt to sort the array `[4, 3, 2, 1]` with insertion sort will be like this: We start looking at the second element (`3, i = 1`) then we compare it with the previous one (`4, i - 1 = 0`), we see that those element are not sorted, then we have to swap them. The operation is as follows: `[4, 3, 2, 1] -> [3, 4, 2, 1] // 1 swap` Now the first 2 elements are in order and we reached the beginning of the array. Next, we need to increment `i` to look for the next element and swap it back to his place. In this case the number `2` is two swaps away from his place: `[3, 4, 2, 1] -> [3, 2, 4, 1] -> [2, 3, 4, 1] // 2 swaps` For the last element the logic is the same. The operation goes like this: `[2, 3, 4, 1] -> [2, 3, 1, 4] -> [2, 1, 3, 4] -> [1, 2, 3, 4] // 3 swaps` So at the end we need 6 swaps to sort the array. ## First Attempt Knowing this, we could start with a simple solution for the problem. Implement the insertion sort and count every time we make a swap: ```java public static int insertionSort(List arr) { int swaps = 0; // this loop iterates over the array starting with the second element. for (int i = 1; i < arr.size(); i++) { int j = i; // this loop iterates back over the i previous elements or until the i elem // reaches his place and swaps when is necessary. while (j > 0 && arr.get(j) < arr.get(j - 1)) { swap(arr, j, j-1); swaps++; j--; } } return swaps; } ``` This solution is correct, but it takes too much time. The time complexity is in the worst case quadratic O(n^2), just like the insertion sort. This in not good enough, we need a better solution to this problem. ## Understanding the solution Another way of thinking this problem is this: if we make pairs of all the elements in the array in the original order, we will need as many swaps as unsorted pairs. For example, for the first array `[4, 3, 2, 1]` all the pairs are `[4, 3] [4, 2] [4, 1] [3, 2] [3, 1] [2, 1]`. In this case all the six pairs are unsorted and it will take 6 swaps to sort it using insertion sort. It’s easy to see that for a sorted array there will be zero unsorted pairs, and then the swaps to sort it are 0. Using this approach we can make a code that iterates through all the pairs in the array, and count them: ```java public static int insertionSort(List arr) { int swaps = 0; for (int i = 0; i < arr.size() - 1; i++) { for (int j = i + 1; j < arr.size(); j++) { if (arr.get(j) < arr.get(i)) { swaps++; } } } return swaps; } ``` This looks better, but is in practice worse than sorting the array and counting. The time complexity of this algorithm will be always quadratic *O(n^2)*, while the insertion sort is quadratic in the worst case, but could be better (linear if the array is sorted). Looks like we are worse than at the start, but now we have a deeper understanding of the insertion sort, and we know how to calculate the swaps without actually swapping the elements, we just need a better way of calculating the unsorted pairs, and this will give us the solution of the swaps required to sort the array using insertion sort. ## Divide And Conquer What about using one of the most efficient sorting techniques to count the unsorted pairs ? This could give a better time solution of we manage to do it. Let’s try it out with an example with the array `[12 15 1 5 14 6 11]` counting the unsorted pairs we know that 11 swaps will be need it, let’s try to calculate that using divide and conquer: 1. First we will divide until we have a problem with a trivial solution (1 element is always sorted): `[12 15 1 5] [14 6 11]` `[12 15] [1 5] [14 6] [11]` `[12]-[15] [1]-[5] [14]-[6] [11]` 2. After that we should start merging the arrays and count the unsorted pairs `[12 15] [1 5] [6 14] [11]` // **1 swap** the first two arrays (and the last one) where already sorted, and no swaps where needed. But the 3rd array was unsorted, so we needed to swap it. 3. Let’s continue merging and counting: `[12 15] merge [1 5] -> [1] -> [1 5] -> [1 5 12] -> [1 5 12 15]` // **4 swaps** when we merge this two arrays, how we count the swaps? well is not that hard: every time we put a number in the merged array from the right array we need to account for the “swaps” we made. In the first case when we put the 1, we would need to do 2 swaps to put it there, because there are two elements in the left array. The same is for the six, so to order this half we need **4 more swaps**. `[6 14] merge [11] -> [6] -> [6 11] -> [6 11 14]` // **1 swap** In this case we first merge the `6`, but it was already on his place, in the left array (no swaps were needed). After, we add the `11` in this case there were remaining items on the left array, so we need to account for the swaps. There was only 1 element in the left array when we merge the `11` so we only need **1 swap**. Finally, we merge the `14` from the left array, this doesn’t sum up any swaps. 4. The final merge: `[1 5 12 15] merge [6 11 14]` `-> [1]` // merged element from the left array, no swaps `-> [1 5]` // merged element from the left array, no swaps `-> [1 5 6]` // merged element from the right array, **2 swaps** (the elements remaining on the left array [12 15]) `-> [1 5 6 11]` // merged element from the right array, **2 swaps** (the elements remaining on the left array [12 15]) `-> [1 5 6 11 12]`// merged element from the left array, no swaps `-> [1 5 6 11 12 14]`// merged element from the right array, **1 swap** (the element remaining on the left array [15]) `-> [1 5 6 11 12 14 15]` // merged element from the left array, no swaps The total amount of swaps calculated is **11**, which is the same number of unsorted pairs. It works! Now we have the idea to implement a *O(n log n)* (which is better than *O(n^2)*) algorithm to count the swaps needed to sort with insertion sort. Let’s do it: ```java class InsertionSortAdvancedAnalysis { private static long swaps; public static long insertionSort(List arr) { swaps = 0; sort(arr); return swaps; } private static List sort(List array) { if (array.size() == 1) { return array; } else { List left = getLeftHalf(array); List right = getRightHalf(array); return merge(sort(left), sort(right)); } } private static List merge(List left, List right) { int leftI = 0; int rightI = 0; List result = new ArrayList<>(); // Merge Both Arrays while (bothHalfsHaveElements(left, right, leftI, rightI)) { if (nextElementsAreOrdered(left, right, leftI, rightI)) { addLeftElementToResult(left, leftI, result); leftI++; } else { // Here we insert from the right half and have to sum swaps addRIghtElementToResult(right, rightI, result); rightI++; swaps += left.size() - leftI; } } // Fill with the remaining if (leftHalfHasRemainingElements(left, leftI)) { result.addAll(left.subList(leftI, left.size())); } else { result.addAll(right.subList(rightI, right.size())); } return result; } private static List getRightHalf(List array) { return array.subList(array.size() / 2, array.size()); } private static List getLeftHalf(List array) { return array.subList(0, array.size() / 2); } private static boolean leftHalfHasRemainingElements(List left, int leftI) { return leftI < left.size(); } private static void addRIghtElementToResult(List right, int rightI, List result) { result.add(right.get(rightI)); } private static boolean bothHalfsHaveElements(List left, List right, int leftI, int rightI) { return leftI < left.size() && rightI < right.size(); } private static void addLeftElementToResult(List left, int leftI, List result) { addRIghtElementToResult(left, leftI, result); } private static boolean nextElementsAreOrdered(List left, List right, int leftI, int rightI) { return left.get(leftI) <= right.get(rightI); } public static void main(String[] args) { List arr = List.of(2,1,3,1,2); System.out.println(4999950000L); System.out.println(Integer.MAX_VALUE); } } ``` There is one last thing to get all the green tests in HackerRank, you will need to change the returning type of the method from int to long, because the results are too large for an int. Hope you enjoyed the walk through!

earosselot

Insertion Sort Advanced Analysis (Hacker Rank Solution)

Join Our Newsletter. No Spam, Only the good stuff.