Welcher ist der richtige Bubble Sort und welcher ist besser?

Question

Ich hatte einen Streit mit einem Freund über die wirkliche Blase Art der folgenden beiden Algorithmen, und über die man besser ist, nicht zu erwähnen, die eine Mine ist, ich will nur Ihre Antworten auf diese beiden Fragen zu diesen beiden Algorithmen hören (geschrieben in C++)

1-, welches die reale Blasensortierung?
2-welche ist besser?

hier sind die beiden Algorithmen:

// Number one : 
void BubbleSort(int Arr[], int size) 
{ for (int i=0;i<size-1;i++) 
     for (int j=i+1;j<size;j++) 
      if (Arr[i]>Arr[j]) 
      { int temp = Arr[i]; 
       Arr[i] = Arr[j]; 
       Arr[j] = temp; 
}   } 

// Number two : 
void BubbleSort(int Arr[], int size) 
{ for (int i=0;i<size-1;i++) 
     for (int j=0;j<size-1;j++) 
      if (Arr[j]>Arr[j+1]) 
      { int temp = Arr[j]; 
       Arr[j] = Arr[j+1]; 
       Arr[j+1] = temp; 
}   } 

Answer 1

Nummer zwei auf dem realen näher ist. Alle Vergleiche sollten zwischen benachbarten Elementen liegen.

Aber die eigentliche Blase Art würde eine while Schleife statt einer äußeren for Schleife nehmen und die while Schleife wieder würde nur ausgeführt, wenn Elemente auf dem letzten Durchlauf werden musste getauscht, wie folgt aus:

void BubbleSort(int Arr[], int size) 
{ 
    bool swapped; 
    do { 
     swapped = false; 
     for (int j=0;j<size-1;j++) 
      if (Arr[j]>Arr[j+1]) { 
       int temp = Arr[j]; 
       Arr[j] = Arr[j+1]; 
       Arr[j+1] = temp; 
       swapped = true; 
      } 
    } while (swapped); 
} 

Answer 2

der Pseudo-Code für die verschachtelte Schleife Blasensortierung ist:

procedure bubbleSort(A : list of sortable items) 
    n := length(A)-1 
    for(i=0; i<= n; i++) 
    for(j=n; j>i; j--) 
     if A[j-1] > A[j] then 
      swap (A[j-1], A[j]) 
     end if 
    end for 
    end for 
end procedure 

Dies bedeutet, dass der erste am nächsten, da die innere Schleife iteriert über nur Elemente nach der i. Die zweite Methode, die Sie gezeigt haben, hat eine innere Schleife, die über alle Elemente iteriert, auch wenn Elemente bereits sortiert sind, so dass Sie keine Zeit damit verschwenden müssen.

, dass die erste Methode bedeutet, ist auch besser.

Answer 3

Die Antwort auf Frage # 2: Weder "besser" ist. Beide sind O (n^2) Sortieralgorithmen (die schrecklich sind). Abgesehen von einer Einführung in Sortieralgorithmen ist Bubble Sort nutzlos.