You are here:

C++/Counting Inversions

Advertisement


Question
I am trying to find the number of inversions using merge sort, but I am
having trouble counting up the inversions.  Any feedback would be helpful!

http://paste2.org/p/152928
http://paste2.org/p/152939
http://paste2.org/p/152930

Thank you,

-Xin

Answer
well, the function MergeSort does seem to return the number of inversions. i haven't gone through the code for MergeSort (or Merge for that matter), but it is clear that you are ignoring it's return value in main. should be something like

       // ...
       time(&start_time);
       _ftime(&start_Struct);

       r = MergeSort(dataArray, 0, ARRAYSIZE-1);
       // here, r should have the number of inversions for this sort

       time(&finish_time);
       _ftime(&finish_Struct);
       // ....  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.