Count Inversions in an array | Set 1 (Using Merge Sort) | GeeksforGeeks
Count Inversions in an array | Set 1 (Using Merge Sort) | GeeksforGeeks
Explanation for the article: http://www.geeksforgeeks.org/counting…
This video is contributed by Harshit Jain.
Content
0.59 -> Hello everyone!
1.59 -> And, welcome to GeeksforGeeks.
3.739 -> In this tutorial we are going to see how to
count the number of inversions in an array.
9.1 -> First of all let us try to understand what
do we mean by an inversion.
14.91 -> So an element at index I and element at index
j form an inversion if the value of element
22.16 -> at index i is greater than value of element
at index j whereas value of I is smaller than
29.71 -> value of j.
31.14 -> For example, in the given sequence 2,4,1,3,5
there are a total of 3 inversions.
38.86 -> Let us look at them one by one
So first of all we look at elements 2 and
44.68 -> 1 highlighted in red.
47.19 -> Here 2 > 1 whereas index of 2 < index of 1.
53.44 -> So they form an inversion.
57.26 -> Similarly the element 4 and 1 form an inversion
as 4 > 1 whereas index of 4 is smaller than
65.88 -> index of 1.
68.49 -> Finally we look at element 4 and 3.
71.7 -> They also form an inversion as 4 > 3 but index
of 4 is smaller than index of 3.
79.409 -> In this problem we basically have to find
out the inversion count of the array.
84.469 -> Inversion count actually tells how far or
how close the array is from being sorted.
91.539 -> So if the array is completely sorted, there
will not be any inversions in the array and
96.729 -> thus the inversion count will be zero.
99.469 -> However, if the array is sorted in reverse
order, the inversion count will be the maximum
105.31 -> possible inversion count value for any array
of that size.
111.34 -> First of all, letís look at the simplest
method.
114.439 -> In this method we iterate over the array element
by element and for each element we check the
120.73 -> number of smaller elements to the right of
the selected element.
125.729 -> So you see the method getInvCount, we first
of all initialize inv_count as zero.
131.12 -> Then we run a loop from 0 to n-1 where n is
the total number of elements.
138.629 -> Then for each element, we run a loop from
the element to itís right to element at index
146.069 -> n-1.
147.069 -> Whenever we encounter any element which is
smaller than given element, we increment the
153.73 -> inv_count.
155.569 -> Finally we return the inv_count.
158.61 -> This method solves the problem in Order of
n squared time complexity.
165.04 -> Now weíll look at the solution in which we
will be using enhanced merge sort to count
169.88 -> the number of inversions in an array.
172.69 -> But firstly weíll quickly recapitulate the
original merge sort algorithm.
178.15 -> Merge sort works on divide and conquer paradigm
i.e. we keep recursively dividing the given
184.51 -> problem into smaller sub problems until they
become simple enough to be solved directly,
190.739 -> then solutions of the subproblems are combined
to give solution to the original problem.
198.03 -> Given an array, we first of all divide the
array into two halves.
202.319 -> Then we call the mergeSort on each of those
halves and then we finally merge those two
208.549 -> sorted subarrays.
211.829 -> Here is the big picture of enhanced merge
sort algorithm.
215.56 -> We divide the array recursively into two halves
and compute the answer for those two sub-halves.
222.799 -> Now suppose we know the number of inversions
in the left and right halves of the array,
228.969 -> then what kinds of inversions are not accounted
for in inv1 + inv2 ?
234.81 -> Well the answer is the ones we have to count
during the merge step.
240.409 -> Therefore to get the total number of inversions
we need to add number of inversions in the
245.779 -> left subarray, right subarray and in the merge
step.
251.139 -> Now the question is how do we get the number
of inversions in the merge operation?
256.37 -> To answer that let I be used for indexing
left subarray and j be used for indexing right
263.59 -> subarray.
264.59 -> At any step in merge if value of element at
index i is greater than value of element at
272.09 -> index j, then we know that there are (mid-i)
inversions.
278.49 -> This is because both left and right subarrays
are already sorted, so if element at index
284.83 -> i is greater than element at index j, then
all the elements in the left subarray with
291.43 -> index greater than i will also be greater
than element at index j.
299.06 -> Let us try to understand this with the help
of an example.
302.05 -> So here you have the left and right half of
the array.
307.06 -> Notice that both of these are already sorted
individually.
311.96 -> So we start with index i=0 and index j =3
whereas the mid index is 3 because from index
320.06 -> 3 the right subarray starts.
323.419 -> Also the initial inversion count is set as
Zero.
328.11 -> Now we compare the two highlighted elements.
331.58 -> 1 is smaller than 2, So we move it in the
merged array and the inversion count remains
338.229 -> zero.
339.55 -> Now we compare 3 with 2.
342.22 -> As 3 is greater than 2, weíll move the smaller
element i.e. 2 in the merged array.
348.47 -> But before that we see that we have encountered
an inversion.
352.389 -> Although value of 3 is greater than value
of 2, but the index of element 2 is smaller
358.65 -> than index of 3.
360.639 -> We already know that first subarray is sorted.
364.629 -> So elements coming after 3 will be greater
than 3 and thus will also be greater than
369.69 -> value 2.
371.4 -> So they all form pairs of inversions with
element 2.
375.78 -> So in total we see that there are mid index-i
i.e. 3-1=2 inversions in this step.
384.55 -> So weíll increment the value of inversion
count by 2.
389.05 -> Now we compare 3 with 4.
390.78 -> As 3 is smaller than 4, we move the value
3 to sorted array and increment the value
397.27 -> of i.
400.09 -> Now we compare 5 with 4.
402.919 -> Clearly 5 is greater than 4 but index of 5
is smaller than index of 4.
408.34 -> So we have again found an inversion.
413.07 -> As per our algorithm, weíll add mid index
ñ i i.e. 3-2=1 inversions in the inversion
421.21 -> count.
422.3 -> After that weíll move 4 into the sorted array
and increment the value of index j.
427.909 -> Now we compare 5 with 6.
429.99 -> As 5 is smaller than 6, we move the value
5 to sorted array.
436.75 -> Now as all the elements of left subarray are
already processed, weíll just move the remaining
442.5 -> elements of right subarray to the sorted array.
446.6 -> After all elements are processed and moved
to sorted merged array, we have the inversion
451.46 -> count of the merge step as 3.
455.699 -> Now letís understand the algorithm better
with the help itís implementation.
460.56 -> So the implementation starts with the mergeSort
function which takes as an argument the array
466.759 -> and itís size.
468.9 -> Inside this function, we create a temporary
array and pass it to _mergesort method along
475.21 -> with the original array.
477.449 -> We also pass the starting and ending index
of array i.e. 0 and array_size -1 respectively.
487.289 -> Now lets see the _mergeSort method.
491.189 -> Here we declare the variables mid and inv_count.
494.02 -> We also initialize the inversion count with
value zero.
500.03 -> Here we check if right is greater than left,
then we do the following.
505.67 -> We calculate the value of mid as right + left/2.
510.669 -> Now as per the algorithm, we call the _mergeSort
method for left subarray and right subarray.
518.31 -> Notice that left subarray is from left to
mid index whereas the right subarray is from
524.33 -> mid+1 to right.
527.23 -> We add the inversion counts returned by these
respective calls to inv_count variable.
534.98 -> Finally we call the merge method to merge
the left and right subarrays and add the inversion
540.57 -> count returned by _merge method to inv_count
variable.
545.2 -> Lastly, we return the value of inv_count.
552.63 -> In merge method, we first of all declare variables
i, j and k.
557.63 -> Then we declare inv_count and initialize it
as zero.
563.03 -> Then we initialize variable i as left, j as
mid and k as left.
570.64 -> Then while either one of the array is not
completely processed, we do the following.
576.36 -> We compare the element at index i with element
at index j.
581.31 -> If element at index i is smaller than or equal
to element at index j, then we just copy the
588.18 -> element at index i to temp array and increment
the values of k and i.
595.52 -> Otherwise we copy the value at index j to
temp array and increment the value of both
602.14 -> k and j.
603.14 -> Additionally, as per the algorithm which we
discussed, we encounter the inversions in
609.381 -> this case, so we add mid-i inversions to inv_count.
616.37 -> Once this is done, we copy the remaining elements
of left subarray, if any, to temp array.
623.57 -> Then similarly we copy the remaining element
of the right subarray, if any, to temp array.
630.13 -> Finally, copy the values from temp array back
to our original array and return the inv_count
637.72 -> value.
639.26 -> Now coming to the time complexity.
641.47 -> The time complexity of this solution is same
as of the merge sort algorithm i.e.
647.29 -> O(nlogn) and the algorithmic paradigm used
is Divide and conquer.
653.86 -> So in total we discussed two methods to solve
the problem.
658.23 -> The first one was simple method which solved
the problem in Order of n squared time complexity
663.56 -> whereas the 2nd method using the enhanced
merge sort solved the problem in Order of
669.79 -> n log n time complexity.
673.35 -> So that is all for this tutorial.
675.17 -> Thank you.
Source: https://www.youtube.com/watch?v=k9RQh21KrH8