ist die Anzahl von Iterationen in einem Blasensortieralgorithmus gleich (n-1)! für n Elemente? wird erforderlich <code>n*(n-1)*...*1 = 7!</code>

Question

ich in einem Buch vor kurzem gelesen, dass, wenn wir n Elemente in einem Array, die Anzahl der Iterationen zu sortier.

Aber ich bin sicher, dass die tatsächliche Zahl der Vergleiche wird (n-1) + (n-2) + ... + 1 = n (n-1)/2. Sind die Anzahl der Iterationen und die Anzahl der Vergleiche irgendwie unterschiedlich? Ich vermute, nein, in jeder Iteration, da die Werte verglichen werden [if(m[j]>m[j+1])]. Verpasse ich etwas oder ist das Buch falsch?

Der gesamte Code:

for(i=0;i<7;i++) 
{ 
    for(j=0;j<7-i;j++) 
    { 
     if(m[j]>m[j+1]) 
     { 
      t=m[j]; 
      m[j]=m[j+1]; 
      m[j+1]=t; 
     } 
    } 
} 

Answer 1

Wenn ich die Frage richtig verstanden habe, ist es ein Mißverständnis. Für eine beliebige Anzahl n von Elementen gibt es

n!=1*2*...*(n-1)*n 

verschiedene Möglichkeiten, sie zu organisieren, die auch Permutationen genannt. Dies steht jedoch in keinem Zusammenhang mit einem Sortieralgorithmus. Die asymptotische Laufzeitkomplexität von Bubblesort ist

O(n^2) 

wie Sie bereits erwähnt, als Bubblesort ein bisschen wenig schlauer ist als alle Möglichkeiten auszuprobieren. Um schließlich die richtige Frage zu beantworten, keine, Bubblesort tut nicht nehmen (n-1)! Iterationen auf n Elemente.