-2

I wrote two simplest sorting algorithms that are almost the same, but the one that has more than half operations to perform takes double the time. It is beyond my understanding why that is happening.

Any pointers would be much appreciated since I'm trying to understand the most efficient way to sort, considering different circumstances, a sort as simple as that got me puzzled.

public class Sort{

static long timerStart;
static long timerEnd;
static long passedTime;

public static void main(String[] args) {

        double[] arr = createDoubleArray(10000);
        double[] arr2 = Arrays.copyOf(arr,arr.length);

        startTimer();
        sortDoubleArrayFast(arr);
        stopTimer();
        computationTime();

        startTimer();
        sortDoubleArraySlow(arr2);
        stopTimer();
        computationTime();

}
public static void startTimer(){
    timerStart = System.currentTimeMillis();
}
public static void stopTimer(){
    timerEnd = System.currentTimeMillis();
}
public static void computationTime(){
    passedTime = timerEnd-timerStart;
    System.out.println("The operations took: " +passedTime+"ms");
}
public static double[] createDoubleArray(int size){

    double[] output = new double[size];
    for (int i = 0; i < size; i++) {
        output[i] = Math.random()*10000000;
    }

    return output;
}
public static double[] sortDoubleArraySlow(double[] input){
    double tmp;
    int operationNumber = 0;
    for (int j = 0; j < input.length; j++) {
        for (int i = 0; i < input.length; i++) {
            operationNumber++;
            if(input[i]>input[j]){
                tmp = input[j];
                input[j] = input[i];
                input[i] = tmp;
            }
        }
    }
    System.out.println("Operation number in Slow: "+operationNumber);
    return input;
}
public static double[] sortDoubleArrayFast(double[] input){
    double tmp;
    int operationNumber = 0;
    for (int j = 0; j < input.length-1; j++) {
        for (int i = j+1; i < input.length; i++) {
            operationNumber++;
            if(input[i]>input[j]){
                tmp = input[j];
                input[j] = input[i];
                input[i] = tmp;
            }
        }
    }
    System.out.println("Operation number in Fast: "+operationNumber);
    return input;
}

}

Krzysztof Zabołotny
  • 1
  • 1
  • See: [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – Jacob G. Feb 07 '20 at 21:20
  • 4
    `double[] arr2 = arr;` means when you call `sortDoubleArraySlow(arr2);` you are passing a *sorted array* to `sortDoubleArraySlow`. – Elliott Frisch Feb 07 '20 at 21:26
  • 3
    Elliott got it. In addition do never forget that Java programs start slowly and become faster after an initial warmup phase. This is mainly caused by the class-loading and memory management. You should repeat the tests several times until the time per iteration does not change anymore. Then use the stable measurements. – Stefan Feb 07 '20 at 21:35
  • Sir, but the variable assignment happens before the sort, so in the first sort, the state of arr2 is not changed. And furthermore, the time difference is the same if I isolate the two sorts, and do the separately. – Krzysztof Zabołotny Feb 07 '20 at 21:35

1 Answers1

0

I am surprised that this question got downvoted because as you can see from the comments, the answer is not at all obvious. The answer to your question is "relatively" simple - JIT. When we have a loop that does exactly the same thing every time, JIT turns it into a piece of native code and executes it directly. However, when we change the inner loop every execution (change of start i = j + 1), then JIT does not work, so JVM must reinterpret it, which already causes time overhead.

kryzystof
  • 190
  • 2
  • 13