Inversion count Important

Revision en2, by Shellhead96, 2018-07-17 14:25:42

Statement of question is this. I read an approach to this question on stack overflow and it is :

1. Merge sort array A and create a copy (array B)

2. Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.

2a. accumulate the number of inversions to counter variable num_inversions.

2b. remove A[1] from array A and also from its corresponding position in array B
rerun from step 2 until there are no more elements in A.

Here’s an example run of this algorithm. Original array A = (6, 9, 1, 14, 8, 12, 3, 2)

1: Merge sort and copy to array B

B = (1, 2, 3, 6, 8, 9, 12, 14)

2: Take A[1] and binary search to find it in array B

A[1] = 6

B = (1, 2, 3, 6, 8, 9, 12, 14)

6 is in the 4th position of array B, thus there are 3 inversions. We know this because 6 was in the first position in array A, thus any lower value element that subsequently appears in array A would have an index of j > i (since i in this case is 1).

2.b: Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed).

A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3: Rerun from step 2 on the new A and B arrays.

A[1] = 9

B = (1, 2, 3, 8, 9, 12, 14)

9 is now in the 5th position of array B, thus there are 4 inversions. We know this because 9 was in the first position in array A, thus any lower value element that subsequently appears would have an index of j > i (since i in this case is again 1). Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed)

A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)

Continuing in this vein will give us the total number of inversions for array A once the loop is complete.

Step 1 (merge sort) would take O(n * log n) to execute. Step 2 would execute n times and at each execution would perform a binary search that takes O(log n) to run for a total of O(n * log n). Total running time would thus be O(n * log n) + O(n * log n) = O(n * log n).

My question is in case of repeating elements like [4,7,4] what if we modify binary search for finding first occurrence of that element and using erase in vectors to erase the element. What will be the time complexity then ? According to me it is still O(nlogn).

Thanks in advance.

Tags #merge sort, #binary search, #vectors

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Shellhead96 2018-07-17 14:25:42 13 Tiny change: ' elements what if w' -> ' elements like [4,7,4] what if w'
en1 English Shellhead96 2018-07-17 14:23:30 2706 Initial revision (published)