Timing bubble sorting in different scenarios

Question

I am trying determine the running times of bubble sort algorithm in three different kinds of input:

1) randomly selected numbers
2) already sorted numbers
3) sorted in reverse order numbers

My expectation about their running time was:

Reverse ordered numbers would take longer than other two.
Already sorted numbers would have the fastest running time.
Randomly selected numbers would lie between these two.

I've tested the algorithm with inputs containing more than 100.000 numbers. The results wasn't like I expected. Already sorted numbers had the fastest running time but randomly selected numbers took almost twice as much time to execute compared to reverse ordered numbers. I was wondering why this is happening?

Here is how I test the inputs

    int[] random = fillRandom();
    int[] sorted = fillSorted();
    int[] reverse = fillReverse();

    int[] temp;
    long time, totalTime = 0;

    for (int i = 0; i < 100; i++) {
        temp = random.clone();
        time = System.currentTimeMillis();
        BubbleSort.sort(temp);
        time = System.currentTimeMillis() - time;
        totalTime += time;
    }
    System.out.println("random - average time: " + totalTime/100.0 + " ms");

    totalTime = 0;
    for (int i = 0; i < 100; i++) {
        temp = sorted.clone();
        time = System.currentTimeMillis();
        BubbleSort.sort(temp);
        time = System.currentTimeMillis() - time;
        totalTime += time;
    }
    System.out.println("sorted - average time: " + totalTime/100.0 + " ms");

    totalTime = 0;
    for (int i = 0; i < 100; i++) {
        temp = reverse.clone();
        time = System.currentTimeMillis();
        BubbleSort.sort(temp);
        time = System.currentTimeMillis() - time;
        totalTime += time;
    }
    System.out.println("reverse - average time: " + totalTime/100.0 + " ms");

Trying to time Java code that way is going to produce effectively useless results. See [this question](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) for some information on how to do it correctly. — resueman, Oct 17 '16 at 20:09
Use a warm-up, i.e. run the sort, say, 100 times WITHOUT timing it, then take the time. Do this for each variant independently, i.e. not one after the other. Turn off GC. Even then, results may be counter-intuitive. One thing that could help explain the reverse order case is [branch prediction](http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array/11227902#11227902). — Markus Fischer, Oct 17 '16 at 20:13

score 0 · Answer 1 · answered Oct 17 '16 at 21:33

Benchmarks for java code are not easy, as JVM might apply a lot of optimizations to your code at runtime. It can optimize out a loop if computation result is not used, it can inline some code, JIT can compile some code into native and many other things. As a result, benchmark output is very unstable.

There are tools like jmh that simplify benchmarking a lot.

I recommend you to check this article, it has an example of benchmark for sorting algorithm.

Timing bubble sorting in different scenarios

1 Answers1