Insertion Sort Advanced Analysis

Problem Statement of Insertion Advanced Analysis Challenge

An array of integers of size n is given. Find the number of shift operations done if the array is sorted using insertion sort. The original problem statement of Insertion Sort Advanced Analysis challenge is available at Hackerrank.

Basic O(n2) Approach

Basic approach to solve this problem is apply insertion sort on the given array and count the total number of shifts done during the process. For instance

Given Array => [5, 2, 1, 9, 7, 12, 4, 3]
Insertion sort passes =>
[2, 5, 1, 9, 7, 12, 4, 3] — # of shifts = 1
[1, 2, 5, 9, 7, 12, 4, 3] — # of shifts = 2
[1, 2, 5, 9, 7, 12, 4, 3] — # of shifts = 0
[1, 2, 5, 7, 9, 12, 4, 3] — # of shifts = 1
[1, 2, 5, 7, 9, 12, 4, 3] — # of shifts = 0
[1, 2, 4, 5, 7, 9, 12, 3] — # of shifts = 4
[1, 2, 3, 4, 5, 7, 9, 12] — # of shifts = 5

Total number of shifts = 1+2+0+1+0+4+5 = 13 13 is correct answer but this solution requires full execution of insertion sort which will cost O(n2).

Time Efficient O(nlogn) Approach

To get best time Merge Sort can be used. But the question is how to count number of shifts in insertion sort while using Merge Sort. This is the reason the problem is called Advanced Analysis of Insertion Sort.

In Merge Sort algorithm first the array is divided into two halves. These two halves are sorted using merge sort recursively. Then these two sorted halves are merged into one sorted array. The point to be noticed here is the elements in first half belong to the first half of the original array. Similarly elements in second half remain in second half throughout the complete process until these two halves are merged together.

Insertion Sort Advanced Analysis

Consider the above two halves. Suppose we are merging them. At any point ith element X of first half and jth element Y of second half are compared. Whichever is smaller will go first in the merged array. There are three possibilities – X < Y, X == Y and X > Y. If it is insertion sort then in case of X > Y only shifting is required because in this case only X will come in the right of Y. As both halves are sorted, so all the elements from ith index till last index p are greater than Y and need to be shifted for Y. So total shifts corresponding to Y will be p-i+1. In this way we can count the shifts done in insertion sort without actually doing any shifts. Lets see an elaborate example-

The given array is [5, 2, 1, 9, 7, 12, 4, 3] same as taken above.

Merge sort will run as follows-

Insertion Sort Advanced Analysis

Counting Shifts In Merge Sort

Insertion Sort Advanced Analysis

Explanation :

Merging of [5] and [2] : 2 is in right half and smaller than 5 so shifts corresponding to 2 is 1.

Merging of [1] and [9] : 9 is not smaller than 1 so no shift.

Merging of [7] and [12] : 12 is not smaller than 7 so no shift.

Merging of [4] and [3] : 3 is in right half and smaller than 4 so number of shifts corresponding to 3 is 1.

Merging of [2, 5] and [1, 9] : 1 is in right half and smaller than 2 so number of shifts corresponding to 1 is 2 (2 remaining elements from 2 to 5).

Merging of [7, 12] and [3,4] :  3 is in right half and smaller than 7 so number of shifts corresponding to 3 is 2 (2 remaining elements from 7 to 12). 4 is in right half and smaller than 7 so number of shifts corresponding to 4 is 2 (2 remaining elements from 7 to 12).

Merging of [1, 2, 5, 9] and [3, 4, 7, 12] : 3 is in right half and smaller than 5 so number of shifts corresponding to 3 is 2 (2 remaining elements from 5 to 9). 4 is in right half and smaller than 5 so number of shifts corresponding to 4 is 2 (2 remaining elements from 5 to 9). 7 is in right half and smaller than 9 so number of shifts corresponding to 7 is 1 (1 remaining elements from 9 to 9).

Total number of shifts = 13.

The same answer has been achieved without using insertion sort. The time complexity of this approach is O(nlogn).

Recommended Posts-
Append and Delete
Circular Array Rotation
Organizing Containers of Balls
Can we ditch python for competitive coding?
5 C functions for competitive programming?
Prefix Sum : Query Time O(1) : Pre-processing Time O(n)

Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *