Correct runtime analysis on a Bubblesort-algorithm

Question

Hey I did a runtime analysis on Bubblesort and I wanted to ask you if there were any mistakes since I was not sure at a certain point

heres an extract of the algorithm:

boolean sorted = false;
        while(!sorted)
        {
            int a = 0;
            int b = 1;
            sorted = true;
            while(a < sortArray.length  && b < sortArray.length)
            {
                if(sortArray[a].getWertigkeit() < sortArray[b].getWertigkeit())
                {
                    Karte tmp1 = sortArray[a];
                    Karte tmp2 = sortArray[b];
                    sortArray[a] = tmp2;
                    sortArray[b] = tmp1;
                    sorted = false;
                }

                a++;
                b++;
            }
        }

So the problem I got is in the first while-loop, I solved it as following:

• Best Case: In the best Case the sorted never gets set back to the false (through the if(..){..}) so it only goes once through the loop; So the runtime is, if I am not wrong, 2*2n*1 = 4n => O(n) for the best Case;

• Worst Case:In the worst Case the variable sorted gets set on false everytime the loop starts, as far as I know, so it needs another "n" comparisons so the runtime should be: n*2n*1 = 2n^2 => O(n^2)

I am really not sure if my thoughts about the while(!sorted) are correct or if the runtime makes any sense (since the big o notation seems fine, but im not sure about the precise runtime)

I really hope that my problem is relatable and I look forward to hear from you.

Thx already

Answer 1

Your analysis of the best-case runtime of O(n) is correct. Nice job!

For the worst-case, you need to be a little bit more precise. You're right that every time the flag gets reset you have to make another pass over the array to get it more sorted than before, so you know it's going to be O(n) times the number of times the loop runs. What you haven't yet done in your analysis is talk about how many times that loop can run before everything is going to end up sorted.

One observation you can make about bubble sort is that after the first pass over the array, the largest element is guaranteed to be in the last position - can you explain why? After the second pass, the second-largest element is guaranteed to be in the second-to-last position - again, can you explain why? Based on this pattern, can you argue why the number of times the outer loop runs is at most O(n)?