CODEWITHSUNDEEP
javasortingtime-complexity
Pareidolia
Pareidolia

Reputation: 199

Sorting time always different from first sort

I wrote couple sorting algorithm. I want to compare their sorting times, at least nearly. But after first loop all sorting times decreasing except StoogeSort. I think something optimizating at background but which measure should I consider? First one or the others? And why is this happening?

    public static void main(String[] args) {
    RandomNumber rn = new RandomNumber();

    Scanner sc = new Scanner(System.in);
    while(true){
        System.out.println("Enter the input size.");
        int n = sc.nextInt();
        int[] experimentalArray = rn.experimentalArrayGenerator(n);



        Stopwatch sw1 = new Stopwatch();
        StoogeSort ss = new StoogeSort(experimentalArray.clone());
        System.out.println("StoogeSort : " + sw1.elapsedTime() + " µs");

        Stopwatch sw2 = new Stopwatch();
        RadixSort rs = new RadixSort(experimentalArray.clone());
        System.out.println("RadixSort : " + sw2.elapsedTime() + " µs");

        Stopwatch sw3 = new Stopwatch();
        ShakerSort shs = new ShakerSort(experimentalArray.clone());
        System.out.println("ShakerSort : " + sw3.elapsedTime() + " µs");

        Stopwatch sw4 = new Stopwatch();
        MaximumSubarray ms = new MaximumSubarray();
        int a = ms.maxSubArraySum(experimentalArray.clone());
        System.out.println("MaximumSubarray : " + sw4.elapsedTime() + " µs");
        System.out.println("------------------------------------------------------");
    }
}

Output after 4 loop:

enter image description here

Upvotes: 1

Views: 79

Answers (1)

Janus Varmarken
Janus Varmarken

Reputation: 2336

Microbenchmarking is a complicated matter as many factors influence the execution time (e.g. just-in-time compilation and garbage collection as noted by Jon Skeet in the comments).

You should read this document by Peter Sestoft if you want to gain an understanding of how you should approach microbenchmarking.

Quoting the abstract of the document here, as the document is an external resource:

Sometimes one wants to measure the speed of software, for instance, to measure whether a new way to solve a problem is faster than the old one. Making such time measurements and microbenchmarks requires considerable care, especially on managed platforms like the Java Virtual Machine and Microsoft’s Common Language Infrastructure (.NET), or else the results may be arbitrary and misleading.

Here we give some advice on running microbenchmarks, in particular for managed platforms. Most examples are in Java but the advice applies to any language executed on a managed platform, including Scala, C# and F#. This version uses Java functional interfaces and requires Java 8.

Upvotes: 1

Related Questions