0

I have written a mergesort(divide and conquer) algorithm and I want to use the following arrays to test if the inversion works efficiently..

So, i would just want to confirm the inversion for each of the following arrays .

1. {10,2,3,22,33,7,4,1,2} = 13
2. {4,5,6,1,2,3} = 9
3. {1,20,6,4,5} = 5
4. {3,1,2,0,4} = 5

are all these correct? I do know a question similar has been asked but I just want to confirm if my calculation was correct. with that, I can test my algorithm.Also, this is not an homework. I just want to be so so sure that I have the write inversion count so that i can test it against my code..

helpdesk
  • 1,984
  • 6
  • 32
  • 50
  • 2
    Write a less clever and more straightforwardly correct implementation of inversion counting (i.e. compare everything with everything) and see if the results match. – millimoose Jul 02 '13 at 23:13
  • 1
    Then for good testing you can generate random sequences with random length and do the same check. – Karoly Horvath Jul 02 '13 at 23:30

1 Answers1

0

No.

Your output for the first case should be 22. Also this is not how you check the efficiency of your code. You should try to check in some competitive programming sites for similar kind of problems. For example there a problem in spoj for Counting inversion. Here is the link:

http://www.spoj.com/problems/INVCNT/

Try submitting it there.

banarun
  • 2,305
  • 2
  • 23
  • 40