2
$\begingroup$

This is a homework. It looks easy, but not really.

A list of integers $a_n$, for every $i<j$, if $a_i>2a_j$, then it is an inversion. Count the inversions in the list, and return the count and the ordered list. Note, here the order is defined by the condition, not just sort the integers.

The easiest way is double loop, but it will be a $O(n^2)$ algorithm. So I think I should try divide and conquer, by modify the merge sort algorithm. I think I could get a $O(n \log n)$ algorithm. But I found, while merging and counting cross-halve inversions, I have to scan all the elements in both left halve and right halve. Equivalent to a double loop.

For example:

[8] [6, 3]

8 and 6 are not inversion, 6 and 3 are not inversion, but 8 and 3 are inversion. I have scan all the elements to make sure there's no exception.

Another example:

[2, 7] [1, 5]

There no inversion in either halve, but 7 and 1 are inversion.

I am thinking may be there's a function, and I can define $b_n=f(a_n)$, then I can treat $b_n$ as normal merge sort problem. But I could not figure it out.

$\endgroup$
  • $\begingroup$ "I have to scan all the elements in both left halve and right halve. Equivalent to a double loop." - that's not true, cause both halves are already sorted when you're performing the merge. $\endgroup$ – HEKTO Aug 30 '14 at 18:03
  • $\begingroup$ "return the count and the ordered list" - What ordered list? List of what? This appears out of the blue; you haven't defined it. Please edit the question to specify the problem statement more carefully. $\endgroup$ – D.W. Aug 31 '14 at 6:22
  • $\begingroup$ Hint: an algorithm that removes all inversions might provide a neat point at which to count them. $\endgroup$ – Raphael Sep 1 '14 at 10:29
1
$\begingroup$

The "Merge and Count" step with more explanations. You have two sorted lists - left one and right one. You need to merge them and concurrently count inversions. I'll be talking about regular inversions, not yours - your job is to extend this description. You have a current position in each list. Initially this position is 0 (the beginning of the list), and it can also point after the end of the list.

  • if both current positions are inside their lists, then we have two cases: the left current element is less than the right current element and vice versa. In the first case we just copy the left current element into the resulting list and increment the left position. In the second case we copy the right current element into the resulting list and increment the right position and increment the inversions count by the number of remaining elements in the left list (including the left current element).

  • else if there are no left elements anymore, then we append the remaining right list to the resulting list

  • else we append the remaining left list to the resulting list

So, sometimes this algorithm adds more than one inversion to the inversions count - this allows it to work faster than $O(n^2)$.

$\endgroup$
  • $\begingroup$ I know the regular inversion counting very well, and you just repeated it to me...but I do get some hint and solved the problem, so thank you :P $\endgroup$ – David S. Aug 31 '14 at 23:45
2
$\begingroup$

You can do the counting in linear time for each merge step by iterating over the right list and keeping track of the following information regarding the left list:

  • pointers to the first and last element that formed an inversion with the previous element of the right list
  • the number of elements between those pointers

Since this is homework, I'll leave it to you to work out the details and analysis.

$\endgroup$
  • $\begingroup$ previous element of the right list, previous of which element in the right list? $\endgroup$ – David S. Aug 31 '14 at 0:01
  • $\begingroup$ @davidshen84 Previous of the one, we are currently looking at. (Note that the initial sentence suggests that the main loop of the procedure iterates over the right list.) $\endgroup$ – FrankW Aug 31 '14 at 7:19
  • $\begingroup$ for this case [1, 3, 2, 9], [5, 8, 4, 6, 7], there are no inversion for 5 and 8, but there is an inversion for 4. I do not think your algorithm works in this case. Unless, I misunderstood you. $\endgroup$ – David S. Aug 31 '14 at 11:59
  • 2
    $\begingroup$ @davidshen84 - Again: both halves are sorted after the recursive call on them has returned. $\endgroup$ – HEKTO Aug 31 '14 at 15:58
  • $\begingroup$ At first, I was trying to maintain the original order. In the examples, the arrays are not sorted, but there is no inversion. But I realized sorting them will not increase inversion count, and make the problem easier. $\endgroup$ – David S. Aug 31 '14 at 23:47
1
$\begingroup$

THE same problem was discussed by Tim Roughgarden in Coursera algorithms course, see the lecture slides analysis and design of algorithms1 suppose array A = [1, 3, 2, 9,5, 8, 4, 6, 7] split the list into two part using divide and conquer paradigm

count(array A,length n){
  count inversions and then sort
  x=count(1st half of array,n/2);//O(nlogn) count inversions and then sort
  y=count(2nd half of array,n/2);//O(nlogn) count inversions and then sort
  z=countsplitinversions(A,n);//implement this in O(n) time of merging the two sorted lists and count inverions
  return x+y+z;
}

countsplitnversions(array A,length n)
{
  D=output[length=n]
  B=1st sorted array(1st half of array)
  C=2nd sorted array(2nd half of array)
  i=1,j=1
  for k= 1 to n//for merging
    if B[i]<C[j]
      D[k]=B[i];
      i++
    else[C[j]>B[i]]
    D[k]=C[j];
    j++
  end
}

consider [1,3,5] and [2,4,6] so while merging ,due to 2 copied to output there will be 2 inversions(2,3) and (2,5) and when 4 copied to output the split inversion discovered is (4,5)

$\endgroup$
  • 1
    $\begingroup$ it looks like you only read the title of the question, not the content... $\endgroup$ – David S. Sep 4 '14 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.