4
\$\begingroup\$

I've written a program that counts the number of inversions using a Divide and Conquer algorithm, written in C++11.

#include <iostream>
#include <tuple>
#include <vector>

using IntVec = std::vector<int>;

std::tuple<IntVec, long long> count_inv(IntVec xs);
std::tuple<IntVec, long long> count_split_inv(IntVec xs, IntVec ys);

std::tuple<IntVec, long long> count_inv(IntVec xs) {
    int n = xs.size();

    if (n < 2) return std::make_tuple(xs, 0);

    IntVec::iterator middle = xs.begin() + (n / 2);
    IntVec left(xs.begin(), middle);
    IntVec right(middle, xs.end());

    long long left_inv, right_inv, split_inv;
    IntVec as, bs, cs;
    std::tie(as, left_inv) = count_inv(left);
    std::tie(bs, right_inv) = count_inv(right);
    std::tie(cs, split_inv) = count_split_inv(as, bs);
    return std::make_tuple(cs, left_inv + right_inv + split_inv);
}

std::tuple<IntVec, long long> count_split_inv(IntVec xs, IntVec ys) {
    int n = xs.size() + ys.size();
    IntVec zs(n);
    long long split_inv = 0;

    int i = 0, j = 0, k = 0;
    for (; k < n && i < xs.size() && j < ys.size(); ++k) {
        if (xs[i] <= ys[j]) {
            zs[k] = xs[i];
            ++i;
        } else {
            zs[k] = ys[j];
            ++j;
            split_inv += xs.size() - i;
        }
    }

    for (; i < xs.size(); ++k, ++i)
        zs[k] = xs[i];

    for (; j < ys.size(); ++k, ++j)
        zs[k] = ys[j];

    return std::make_tuple(zs, split_inv);
}

int main() {
    std::vector<int> xs;
    int x;
    while (std::cin >> x) {
        xs.push_back(x);
    }

    IntVec ys;
    long long inv;
    std::tie(ys, inv) = count_inv(xs);
    std::cout << inv << std::endl;
    return 0;
}

I find that the code is very verbose in some areas, such as specifying the type of the tuple. Also, parts of it are confusing. How could I rewrite this code such that it is more concise and clearer?

\$\endgroup\$
  • \$\begingroup\$ Number of inversions of what? And according to which rules? Also, it's "divide and conquer", not the other way around... \$\endgroup\$ – Deduplicator Oct 25 '15 at 17:15
  • \$\begingroup\$ @Deduplicator Whoops, no idea why I wrote it that way. It should print out the number of inversions of the array of numbers, assuming that the numbers are to be sorted in ascending order. \$\endgroup\$ – wei2912 Oct 27 '15 at 14:46
  • \$\begingroup\$ Do you mean number of swaps, instead of inversions? I'm whistling in the dark here, as I still have no idea what your program does (should do), or why... \$\endgroup\$ – Deduplicator Oct 27 '15 at 14:52
  • 1
    \$\begingroup\$ @Deduplicator I believe that an inversion is a pair of array entries that are in the wrong order. In other words every pair (i,j) where i < j && array[i] > array[j]. At least, this is what would make sense, because this program is using the "mergesort method" of counting the number of inversions in an array. See this link, for example. \$\endgroup\$ – JS1 Oct 27 '15 at 20:12
  • \$\begingroup\$ What JS1 wrote is what I'm looking for. I do not need to find the inversions themselves, just the number of inversions. \$\endgroup\$ – wei2912 Oct 28 '15 at 13:29
2
\$\begingroup\$

More clear by using extra argument?

If you passed in a count by reference to each function, and each function incremented this count instead of returning a new count in a tuple, the code might look cleaner. For example, this:

IntVec as, bs, cs;
std::tie(as, left_inv) = count_inv(left);
std::tie(bs, right_inv) = count_inv(right);
std::tie(cs, split_inv) = count_split_inv(as, bs);
return std::make_tuple(cs, left_inv + right_inv + split_inv);

would become this:

IntVec as = count_inv(left, count);
IntVec bs = count_inv(right, count);
return count_split_inv(as, bs, count);

And in main(), this:

long long inv;
std::tie(ys, inv) = count_inv(xs);

would become this:

long long inv = 0;
count_inv(xs, inv);
\$\endgroup\$
  • \$\begingroup\$ I'm not certain if it's good practice to use pointers in this case. \$\endgroup\$ – wei2912 Nov 3 '15 at 14:36
  • \$\begingroup\$ @wei2912 As opposed to creating tuples and returning them? Why are you opposed to using pointers? \$\endgroup\$ – JS1 Nov 3 '15 at 18:10
  • \$\begingroup\$ It certainly looks cleaner, but in these calls to count_inv(xs, inv), it's not entirely clear that the inv/count variables will be changed as a side-effect. I also agree that returning a tuple is much worse, so I don't have an imediate solution for this. \$\endgroup\$ – Cássio Renan Jan 28 '16 at 11:31

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.