Lequel est le vrai Bubble Sort, et lequel est le meilleur?

Question

J'ai eu une dispute avec un ami sur le vrai type de bulle des deux algorithmes suivants, et sur lequel est le meilleur, sans mentionner lequel est le mien, je veux juste entendre vos réponses sur ces deux questions sur ces deux algorithmes (écrit en C++)

1-quel est le véritable type de bulle?
2-lequel est le meilleur?

voici les deux algorithmes:

// 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

numéro deux est plus proche du réel. Toutes les comparaisons doivent être entre des éléments adjacents.

Mais le genre véritable bulle prendrait une boucle while au lieu d'une boucle for extérieure, et la boucle while exécuterait à nouveau que si les éléments devaient être échangés sur la dernière passe, comme ceci:

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

le pseudo-code pour le tri à bulles de boucle imbriquée est:

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 

Cela signifie que le premier est le plus proche parce que la boucle intérieure que sur des éléments après itère i. La deuxième méthode que vous avez montrée a une boucle interne qui itére sur tous les éléments, même si les éléments avant que j'ai été déjà triés, donc il n'y a pas besoin de perdre du temps sur eux.

Cela signifie que la première méthode est également meilleure.

Answer 3

La réponse à la question 2: Aucun n'est «meilleur». Les deux sont O (n^2) algorithmes de tri (qui sont terribles). Autre qu'une introduction aux algorithmes de tri, Bubble Sort est inutile.