Insertion Sort Advanced Analysis on Hacker Rank

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:

public static int insertionSort(List<Integer> 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:

public static int insertionSort(List<Integer> 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:

class InsertionSortAdvancedAnalysis {

    private static long swaps;

    public static long insertionSort(List<Integer> arr) {
        swaps = 0;
        sort(arr);
        return swaps;
    }

    private static List<Integer> sort(List<Integer> array) {
        if (array.size() == 1) {
            return array;
        } else {
            List<Integer> left = getLeftHalf(array);
            List<Integer> right = getRightHalf(array);
            return merge(sort(left), sort(right));
        }
    }

    private static List<Integer> merge(List<Integer> left, List<Integer> right) {
        int leftI = 0;
        int rightI = 0;
        List<Integer> 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<Integer> getRightHalf(List<Integer> array) {
        return array.subList(array.size() / 2, array.size());
    }

    private static List<Integer> getLeftHalf(List<Integer> array) {
        return array.subList(0, array.size() / 2);
    }

    private static boolean leftHalfHasRemainingElements(List<Integer> left, int leftI) {
        return leftI < left.size();
    }

    private static void addRIghtElementToResult(List<Integer> right, int rightI, List<Integer> result) {
        result.add(right.get(rightI));
    }

    private static boolean bothHalfsHaveElements(List<Integer> left, List<Integer> right, int leftI, int rightI) {
        return leftI < left.size() && rightI < right.size();
    }

    private static void addLeftElementToResult(List<Integer> left, int leftI, List<Integer> result) {
        addRIghtElementToResult(left, leftI, result);
    }

    private static boolean nextElementsAreOrdered(List<Integer> left, List<Integer> right, int leftI, int rightI) {
        return left.get(leftI) <= right.get(rightI);
    }

    public static void main(String[] args) {
        List<Integer> 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!