4

I am generating 100,000 random numbers and passing to the sorting function. The numbers are random, meaning that the time taken to sort the array should be more than the best case and less than the worst case. (pardon me if I am wrong, still learning time complexity). It took 25 seconds.

Then, I am passing the same sorted array again to sort function, and it took nearly 0 seconds.

Then, I am reversing the array, thus it should take the maximum number of iteration (swapping) and therefore should take more than 25 seconds of average time complexity. However, it is taking only 8 seconds.

public class BubbleSort {

    private static void sort(int arr[]) {
        int n = arr.length;
        int temp = 0;
        boolean sorted = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    sorted = false;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {

        int arr[] = new int[100000];
        Random rand = new Random();

        for (int i = 0; i < 100000; i++) {
            arr[i] = rand.nextInt(10000000);
        }

        // Avg Case
        long x = System.currentTimeMillis();
        sort(arr);
        long y = System.currentTimeMillis();
        float sec = (y - x) / 1000F;
        System.out.println("avg Case " + sec);

        // Best Case
        x = System.currentTimeMillis();
        sort(arr);
        y = System.currentTimeMillis();
        sec = (y - x) / 1000F;
        System.out.println("Best Case " + sec);

        // Worst Case
        reverse(arr);
        x = System.currentTimeMillis();
        sort(arr);
        y = System.currentTimeMillis();
        sec = (y - x) / 1000F;
        System.out.println("Worst Case " + sec);

    }
}

Here's the output:

avg Case 25.207
Best Case 0.0
Worst Case 8.896
3
  • You haven't posted reverse. Anyways, I've implemented one quickly and I'm able to reproduce your problem. I've checked the sort as well and it's sorting the array. Haven't checked if the bubble sort is correctly implemented though.
    – akuzminykh
    Jul 2 '20 at 10:12
  • 5
    Nothing wrong with your benchmark, or your knowledge that the theory goes that an sorted in reverse should be worst case (most comparisons and swaps) for bubble sort. But you are yet another "victim" of branch prediction. In practice, the CPU is doing optimizations that work well if the data follows certain patterns. On a modern branch-predicting CPU, completely random data is going to be a real-world worst case, because it can not optimize for it, and that is reflected in your results.
    – Michael
    Jul 2 '20 at 10:21
  • @Michael Thanks a lot for specifying that in brief, I went through a branch prediction question but most of the things went over my head. I had a somewhat similar assumption about that optimization but thought it's better to ask than assume. Thanks again! Jul 2 '20 at 11:25