¿Cuál es el tipo de burbuja real y cuál es mejor?

Question

Tuve una discusión con un amigo acerca de la burbuja real de los siguientes dos algoritmos, y sobre cuál es mejor, sin mencionar cuál es el mío, solo quiero escuchar sus respuestas sobre estas dos preguntas acerca de esos dos algoritmos (escrito en C++)

1-¿cuál es el tipo de burbuja real?
2-cuál es mejor?

aquí son los dos algoritmos:

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

número dos está más cercano al real. Todas las comparaciones deben ser entre elementos adyacentes.

Pero el verdadero ordenamiento de burbuja tomaría un bucle while en lugar de un bucle externo for, y el bucle while ejecutaría de nuevo sólo si los elementos tuvieron que ser cambiado en la última pasada, así:

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

el pseudocódigo para la burbuja de bucle anidado tipo es:

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 

Esto significa que la primera es la más cercana debido a que el bucle interior sólo itera sobre elementos después i. El segundo método que mostró tiene un bucle interno que itera sobre todos los elementos, a pesar de que los elementos antes ya se han ordenado, por lo que no hay necesidad de perder tiempo en ellos.

Eso significa que el primer método también es mejor.

Answer 3

La respuesta a la pregunta n. ° 2: tampoco es "mejor". Ambos son algoritmos de ordenamiento O (n^2) (que son terribles). Además de una introducción a los algoritmos de clasificación, Bubble Sort es inútil.