7vies

#include <iostream>
#include <iomanip>

// Timing-related

#ifdef _MSC_VER
#pragma comment(lib, "winmm.lib")
#include <windows.h>
struct Timer {
    Timer() {
        timeBeginPeriod(1);
    }
    ~Timer() {
        timeEndPeriod(1);
    }
    double getTime() {
        DWORD t = timeGetTime();
        return t / 1000.0;
    }
};
#else
#include <sys/time.h>
struct Timer {
    inline double getTime() {
        timeval tv;
        gettimeofday(&tv, 0);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    }
};
#endif

struct Timer2 : public Timer {
    double t;
    void start() {
        t = getTime();
    }
    double end() {
        return getTime()-t;
    }
};

// Helpers

Timer2 timer;
using namespace std;
int* copyarr(int* a0, int N)
{
    int* a = (int*)malloc(sizeof(int)*N);
    memcpy(a, a0, sizeof(int)*N);
    return a;
}

// First bubblesort version

double test1(int* a0, int N)
{
    int i, j;
    int* a = copyarr(a0, N);

    timer.start();

    for (i=0; i<N; i++) {
        for (j=0; j<N - (i+1); j++) {
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);
        }
    }

    double t = timer.end();

    free(a);

    return t;
}

// Second bubblesort version

double test2(int* a0, int N)
{
    int i, j;
    int* a = copyarr(a0, N);

    timer.start();

    for (i=0; i<N-1; i++) {
        for (j=i; j>=0; j--) {
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);
        }
    }

    double t = timer.end();

    free(a);

    return t;
}

const int N = 100000; // array size
int a0[N];

int main()
{
    int i, j;
    for (i=0; i<N; i++) {
        a0[i] = rand();
    }

    double mint1=1e100, mint2=1e100;

    // "fair" test
    for (int k=0; k<3; k++) {
        double t;

        t = test1(a0, N);
        mint1 = min(mint1, t);

        t = test2(a0, N);
        mint2 = min(mint2, t);
    }

    cout << "test1: " << mint1 << endl;
    cout <<  "test2: " << mint2 << endl;
    cout << setiosflags(ios::fixed) << setprecision(2);
    cout << "ratio: " << mint1/mint2 << endl;

    return 0;
}