CODEWITHSUNDEEP
javaalgorithmsortingbubble-sortinsertion-sort
Shiroix3
Shiroix3

Reputation: 11

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

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?

Upvotes: 0

Views: 575

Answers (1)

trincot
trincot

Reputation: 350272

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.

Upvotes: 1

Related Questions