Inverzije...

inversions.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <sys/time.h>

using namespace std;

typedef vector<int> vec;
typedef vector<int>::iterator ix;

struct res {
  vec* v; long cnt;
  res(vec* v, int cnt): v(v), cnt(cnt) {}
  ~res() { delete v; }
};

static res* merge(vec* xs, vec* ys) {

  long invs = 0;
  vec* zs   = new vec (xs->size () + ys->size ());

  ix it = zs->begin (),
     i  = xs->begin (),
     j  = ys->begin ();

  while ( it < zs->end () ) {
    if        ( i == xs->end () ) {
      * it = * j++;
    } else if ( j == ys->end () ) {
      * it = * i++;
    } else if ( *i <= *j ) {
      * it = * i++ ;
    } else {
      * it = * j++;
      invs += ( xs->end () - i );
    }
    ++ it ;
  }
  return new res(zs, invs);
}

static res* inversions(ix start, ix end) {

  int n = end - start;

  if (n <= 1) {
    return new res (new vec (start, end), 0);
  } else {

    res * left  = inversions (start, start + n / 2),
        * right = inversions (start + n / 2 , end);

    res * m = merge (left->v, right->v);
    m->cnt += (left->cnt + right->cnt);

    delete left; delete right;

    return m;
  }
}

vec* read (const char* file) {
  vec *v = new vec;
  ifstream f (file);
  int n;
  while (f.good ()) {
    n = - 19; f >> n; if (n != - 19) v->push_back (n);
  }
  return v;
}

static long now () {
  struct timeval tv;
  gettimeofday (&tv, NULL);
  return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}

const int trials = 100;

const char *data = "dataz.txt";

int main () {

  vec *v = read (data);

  long t0 = now ();

  long n;
  for ( int c = 0; c < trials; ++c ) {
    res* r = inversions(v->begin (), v->end ());
    n = r->cnt;
    delete r;
  }

  long time = now () - t0 ;

  cout << "[time] " << time << " ms (avg: " << (time / trials) << " ms)" << endl;
  cout << "res: " << n << endl;

  return 0;
}