Why is sorting in worst case is taking less time than average case

Viewed 190

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
0 Answers
Related