TestClass for simple sorting algorithms gives unlogical results

Question

I have the following Class with some sorting algorithms like MaxSort, BubbleSort, etc.:

class ArrayUtility {

   public static int returnPosMax(int[] A, int i, int j) {
       int max = i;
       int position = 0;
       for(int c = 0; c <= j; c++){
           if(c >= i){
               if(A[c] > max){
                max = A[c];
                position = c;
                }
           }
       }
      return position;
   }

   public static int returnMax(int[] A, int i, int j) {
      return A[returnPosMax(A, i, j)];
   }

   public static void swap(int[] A, int i, int j) {
       int b = A[i];
       A[i] = A[j];
       A[j] = b;
   }

   public static void MaxSort(int[] A) {
       int posMax;
       for(int i = A.length - 1; i >= 0; i--){
           posMax = returnPosMax(A, 0, i);
           swap(A, posMax, i);
       }
   }

   public static void BubbleSort(int[] A) {
       boolean flag = true;
       while (flag != false){
           flag = false;
           for(int i = 1; i <= A.length - 1; i++){
               if(A[i-1]>A[i]){
                   swap(A, i-1, i);
                   flag = true;
               }
           }
           if(flag = false) {
               break;
           }
           for(int i = A.length - 1; i >= 1; i--){
               if(A[i-1]>A[i]){
                   swap(A, i - 1, i);
                   flag = true;
               }
           }
       }
   }

   public static void BubbleSortX(int[] A) {
       boolean flag = true;
       while (flag != false){
           flag = false;
           for(int i = 1; i <= A.length - 1; i++){
               if(A[i-1]>A[i]){
                   swap(A, i-1, i);
                   flag = true;
               }
           }
       }
   }

}

Now i have to create a Test Class to evaluate the different sorting algorithms for different lengths of randomly created Arrays:

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

public class TestSorting{
    public static void main(String[] args){
        int[] lengthArray = {100, 1000, 10000, 100000};
        for(int i = 0; i <= lengthArray.length - 1; i++){
            int[] arr = new int[i];
            for(int j = 0; j < i; j++){
                Random rd = new Random();
                int randInt = rd.nextInt();
                arr[j] = randInt;
            }
            /* long startTime = System.nanoTime();
            ArrayUtility.MaxSort(arr);
            long cpuTime = System.nanoTime() - startTime;
            System.out.println("Time: " + cpuTime + " - Array with Length: " + lengthArray[i] + " Using MaxSort"); */
            
            /* long startTime = System.nanoTime();
            ArrayUtility.BubbleSortX(arr);
            long cpuTime = System.nanoTime() - startTime;
            System.out.println("Time: " + cpuTime + " - Array with Length: " + lengthArray[i] + " Using BubbleSortX"); */
            
            long startTime = System.nanoTime();
            ArrayUtility.BubbleSort(arr);
            long cpuTime = System.nanoTime() - startTime;
            System.out.println("Time: " + cpuTime + " - Array with Length: " + lengthArray[i] + " Using BubbleSort");
            
            /*long startTime = System.nanoTime();
            Arrays.sort(arr)
            long cpuTime = System.nanoTime() - startTime;
            System.out.println("Time: " + cpuTime + " - Array with Length: " + lengthArray[i] + " Using BubbleSort"); */
        }
    }
}
            

Now when i run a certain sorting algorithm (i set the others as comment for the meantime), i get weird results, for example

Time: 1049500 - Array with Length: 100 Using BubbleSort
Time: 2200 - Array with Length: 1000 Using BubbleSort
Time: 13300 - Array with Length: 10000 Using BubbleSort
Time: 3900 - Array with Length: 100000 Using BubbleSort

And any time i run the test i get different results, such that Arrays with 10 times the length take less time to sort, also i dont understand why the array with 100 integers takes so long.

Answer 1

I took a snippet out of your code to show you where your code is buggy.

 public static void main(String[] args){
    int[] lengthArray = {100, 1000, 10000, 100000};
    for(int i = 0; i <= lengthArray.length - 1; i++) { // this loop goes from 0 - 3
        int[] arr = new int[i]; // thats why this array will be of size 0 - 3
        // correct line would be:
        // int[] arr = new int[lengthArray[i]];
        for(int j = 0; j < i; j++) {
        // correct line would be:
        // for (int j = 0; j < arr.length; j++) {
 ...

Additionally, the hint for benchmarking from Dmitry is also important to note.

Answer 2

TL;DR: your benchmark is wrong.

Explanation

To make a good benchmark, you need to do a lot of research. A good starting point is this article and this talk by Alexey Shipilev, the author of micro-benchmark toolkit JMH.

Main rules for benchmarking:

• warm up! Do a bunch (like, thousands) of warmup rounds before you actually measure stuff - this will allow JIT compiler to do its job, all optimizations to apply, etc.
• Monitor your GC closely - GC event can skid the results drastically
• To avoid that - repeat the benchmark many (hundreds thousands) times and get the average.

All this can be done in JMH.