Sort stupid

.gitignore

qsort
*.swp
*.class

README.md

c++ qsort bench

Makefile

all : g++version clangversion javaversion erlangversion

erlangversion:
	./qsort.escript `cat ./test.args.config`

javaversion:
	javac QuickSort.java && java -cp . QuickSort `cat ./test.args.config`

g++version: 
	g++ -Ofast -o qsort ./qsort.cpp && ./qsort `cat ./test.args.config`

clangversion:
	clang++ -Ofast -o qsort ./qsort.cpp && ./qsort `cat ./test.args.config`

qsort.cpp

#include <stdlib.h>
#include <sys/time.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

typedef vector<int>::size_type vsize_t;

unsigned int time_diff(struct timeval* start, struct timeval* end) {
    return (end->tv_sec * 1000000 + end->tv_usec) - (start->tv_sec * 1000000 + start->tv_usec);
}

void fill_vector(vector<int> &vec, vsize_t size) {
    vec.reserve(size);
    for (vsize_t i = 0; i < size; ++i) {
        vec.push_back(rand());
    }
}

unsigned int test(vsize_t size) {
    vector<int> theVector;
    fill_vector(theVector, size);
    timeval tvStart, tvEnd;
    greater<int> predicate;
    gettimeofday(&tvStart, NULL);
    sort(theVector.begin(), theVector.end(), predicate);
    gettimeofday(&tvEnd, NULL);
    unsigned int elapsedTime = time_diff(&tvStart, &tvEnd);
    cout << "Sort time for " << size << " elements is " << elapsedTime << " micro seconds" << endl;
    return elapsedTime;
}

int main(int argc, char *argv[]) {
    if (argc < 3) {
        cerr << "Usage: qsort <vector size> <loops count>" << endl;
        return EXIT_FAILURE;
    }
    vsize_t vectorSize = atoi(argv[1]);
    int loopsCount = atoi(argv[2]);

    unsigned long acc = 0;
    for (int i = 0; i < loopsCount; ++i) {
        acc += test(vectorSize);
    }
    cout << "Average sort time: " << acc / loopsCount << " micro seconds" << endl;

    cout << "All done" << endl;
    return EXIT_SUCCESS;
}

qsort.escript

#!/usr/bin/env escript

main([SizeStr, LoopsStr]) ->
    Size = list_to_integer(SizeStr),
    Loops = list_to_integer(LoopsStr),
    AllTime =
        lists:foldl(
          fun(_, AccIn) ->
                  Data = [random:uniform(100000) || _ <- lists:seq(1, Size)],
                  T0 = os:timestamp(),
                  lists:sort(fun erlang:'>'/2, Data),
                  ElapsedTime = timer:now_diff(os:timestamp(), T0),
                  io:format("Elapsed time: ~w~n", [ElapsedTime]),
                  AccIn + ElapsedTime
          end,
          0,
          lists:seq(1, Loops)),
    io:format("Average time ~w microseconds~n", [AllTime / Loops]),
    ok.

QuickSort.java

import java.util.Arrays;
import java.util.Random;

public final class QuickSort {

    public static void main(String[] args) throws Exception {
        Random random = new Random();
        int amount = Integer.valueOf(args[0]);
	int loops = Integer.valueOf(args[1]);
	long acc = 0;
	for (int i = 0; i < loops; ++i) {
        	acc += doit(random, amount);
	}
	System.out.format("Average: %d microseconds\n", (acc * 1000) / loops);
    }

    private static long doit(Random random, int amount) {
        int[] array = new int[amount];
        for (int i = 0; i < amount; i++) {
            array[i] = random.nextInt();
        }
        long Start = System.currentTimeMillis();
        Arrays.sort(array);
	long elapsedTime = System.currentTimeMillis() - Start;
        System.out.println(elapsedTime);
	return elapsedTime;
    }

}

sample.output.txt

g++ -Ofast -o qsort ./qsort.cpp && ./qsort `cat ./test.args.config`
Sort time for 500000 elements is 34966 micro seconds
Sort time for 500000 elements is 44317 micro seconds
Sort time for 500000 elements is 28610 micro seconds
Average sort time: 35964 micro seconds
All done
clang++ -Ofast -o qsort ./qsort.cpp && ./qsort `cat ./test.args.config`
Sort time for 500000 elements is 32150 micro seconds
Sort time for 500000 elements is 44345 micro seconds
Sort time for 500000 elements is 25469 micro seconds
Average sort time: 33988 micro seconds
All done
javac QuickSort.java && java -cp . QuickSort `cat ./test.args.config`
94
42
65
Average: 67000 microseconds
./qsort.escript `cat ./test.args.config`
Elapsed time: 462162
Elapsed time: 428279
Elapsed time: 412580
Average time 434340.3333333333 microseconds

test.args.config

500000 3