CODEWITHSUNDEEP
javaalgorithmsortingtime-complexitybubble-sort
user6843846
user6843846

Reputation:

Correct runtime analysis on a Bubblesort-algorithm

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:

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

Upvotes: 2

Views: 175

Answers (1)

templatetypedef
templatetypedef

Reputation: 373472

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)?

Upvotes: 2

Related Questions