korrekte Laufzeitanalyse auf einem Bubblesort-Algorithmus

Question

Hey ich eine Laufzeitanalyse auf Bubblesort tat und ich wollte Dich fragen, ob es irgendwelche Fehler waren, da ich an einem bestimmten Punkt nicht sicher war,

herer ein Extrakt des Algorithmus:

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++; 
      } 
     } 

Also das Problem, das ich in der ersten while-Schleife bekam, ich löste es wie folgt:

• best Case: im besten Fall wird der fals die sortiert nie zurück e (durch das if (..) {..}) so geht es nur einmal durch die Schleife; So ist die Laufzeit, wenn ich nicht falsch bin, 2 * 2n * 1 = 4n => O (n) für den besten Fall;

• Worst Case: Im schlimmsten Fall wird die Variable bei jedem Start der Schleife auf false gesetzt, so weit ich weiß, also braucht es noch einen "n" Vergleich, also sollte die Laufzeit sein: n * 2n * 1 = 2n^2 => O (n^2)

ich bin wirklich nicht sicher, ob meine Gedanken über die while (! sortiert) korrekt sind oder wenn die Laufzeit Sinn macht (da die O-Notation scheint in Ordnung , aber ich bin nicht sicher über die genaue Laufzeit)

Ich hoffe wirklich, dass mein Problem zuordenbar ist und ich freue mich von Ihnen zu hören.

Thx schon

Answer 1

Ihre Analyse der Best-Case-Laufzeit von O (n) ist richtig. Gut gemacht!

Im schlimmsten Fall müssen Sie ein wenig genauer sein. Sie haben Recht, dass jedes Mal, wenn das Flag zurückgesetzt wird, ein weiterer Durchlauf über das Array durchgeführt werden muss, um es sortierter als zuvor zu machen, damit Sie wissen, dass es O (n) mal so oft wie die Schleife läuft. Was Sie in Ihrer Analyse noch nicht gemacht haben, ist, darüber zu reden, wie oft diese Schleife laufen kann, bevor alles sortiert wird.

Eine Beobachtung, die Sie über Blasensortierung machen können, ist, dass nach dem ersten Durchlauf über das Array das größte Element garantiert in der letzten Position ist - können Sie erklären warum? Nach dem zweiten Durchlauf ist garantiert, dass das zweitgrößte Element in der zweitletzten Position ist - auch hier können Sie erklären warum? Können Sie argumentieren, warum die Häufigkeit, mit der die äußere Schleife läuft, höchstens 0 (n) ist?