Way different execution times of Bubble sort and Insertion sort despite the same complexity

Question

I have task to compare 3d Matrix Bubble sort and Insertion sort execution times. They only should sort numbers in each row. I wrote a methods in Java like below:

static void BubbleSort(char tab2D[][], int tabSize) throws InterruptedException {
    for (int i = 0; i < tabSize; i++) {
        for (int j = 1; j < tabSize - i; j++) {
            for (int k = 0; k < tabSize; k++) {
                if (tab2D[k][j - 1] > tab2D[k][j]) {
                    char temp = tab2D[k][j];
                    tab2D[k][j] = tab2D[k][j - 1];
                    tab2D[k][j - 1] = temp;
                }
            }
        }
    }
}
    

static void InsertionSort(char tab2D[][], int size) throws InterruptedException {
    char temp;
    int i, j;
    
    for (int ii = 0; ii < size; ii++) {
        for (i = 1; i < size; i++) {
            temp = tab2D[ii][i];
            for (j = i - 1; j >= 0 && tab2D[ii][j] > temp; j--) {
                tab2D[ii][j + 1] = tab2D[ii][j];
            }
            tab2D[ii][j + 1] = temp;
        }
    }
}

As far as I know both algorithms have time complexity O(n^2), yet there's my results for both algorithms:

100x100 Matrix: Bubble sort=21 ms, Insertion sort=3 ms
300x300 Matrix: Bubble sort=495 ms, Insertion sort=20 ms
700x700 Matrix: Bubble sort=6877 ms, Insertion sort=249 ms

Measuring time like:

start = System.currentTimeMillis();
// sort method
stop = System.currentTimeMillis();
time = stop - start;

I don't really understand where's problem, as Bubble sort is WAY too slow comparing to Insertion. As I understand their times should be similar. Checked even both versions of algorithms editing them to sort only arrays, Bubble sort is still way slower and I can't tell why. Next thing I tried was to put Thread.Sleep(1) in both algorithms just bellow swapping moment. After doing that I realized that times finally look similar and are only just a bit different. Could someone explain why is that happening? Are times I measured before correct?

Time complexity only describes how the runtime of the algorithm behaves if you increase the input size. You could let one algorithm always sleep for 1 hour at the start and it would still have the same time complexity as without the sleep. Therefore, you cannot argue that two algorithms should have the same speed based only on their time complexity. — Turamarth, May 31 '22 at 07:36
How are you measuring the times? Are the input arrays generated randomly? — alchemist, May 31 '22 at 07:37
@Turamarth that was the answer I was looking for, thank you so much. I was confused what actually time complexity meant. — Shiroix3, May 31 '22 at 07:46
as always that will not give correct, reproducible results - this method of measurement is ignoring JIT compiler and other optimizations done by the virtual machine - time performance measurement is very complicated, at least use JMH or similar framework - check [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) (and similar questions) || and as already mentioned, it is not expected that both algorithms have same time performance — user16320675, May 31 '22 at 07:56
You haven’t shown the actual sort invocations. Did you, perchance, sort with bubble sort first and then use insertion sort *on the same (now sorted) data*? Insertion sort terminates quickly on already sorted data, so it’s not a fair comparison if you’re making bubble sort do the actual work. — pjs, May 31 '22 at 11:44
Bubble: inner loop is always `size` iterations; Insertion: inner loop terminates earlier - Bubble: up to 6 array accesses in inner loop; Insertion: at most 3 array accesses in inner loop (array access include index bounds checking) || Related question: [Insertion sort vs Bubble Sort Algorithms](https://stackoverflow.com/q/17270628/16320675) — user16320675, May 31 '22 at 15:49
Why do I read `3d Matrix` in the introductory sentence and `tab2D[][]` in the code? — greybeard, May 31 '22 at 16:16

score 1 · Answer 1 · answered May 31 '22 at 10:35

As mentioned in comments, one cannot say anything useful about the actual time it takes to run an algorithm, based on a given time complexity. Two algorithms that have the same time complexity do not necessarily have to need the same time to complete the same job.

That being said, here are some differences between the two functions that explain why InsertionSort needs less time to do the job on average:

If we ignore the tab2D[ii][j] > temp condition in the inner loop of InsertionSort, both functions perform the same total number of loop iterations. However, as InsertionSort has a condition in the inner loop that can make it exit early, InsertionSort will often make fewer iterations.
Both make a data comparison in their inner loops, but BubbleSort must read two values from the array to do that, while InsertionSort only needs one access to the array (as the other value is in temp)
The inner loop of InsertionSort can focus on one value that bubbles into its right place, meaning it does not actually has to swap, but only copy. BubbleSort has to swap, which involves three assignments instead of one. Granted, BubbleSort does not have to swap in each iteration of its inner loop, but that is offset against the fact that InsertionSort does not move all array values (in the loop's range) either -- as it has this early exit. This gives a feel of BubbleSort doing 3 assignments, where InsertionSort only needs 1 assignment (plus an overhead of 2 assignments outside of the inner loop). We can see that on average BubbleSort will perform more assignments (involving the array) than InsertionSort.

Way different execution times of Bubble sort and Insertion sort despite the same complexity

1 Answers1