Hola pues ya me he liado del todo.
Por qué en el caso más favorable es n^2, no sería 0? Es que creo que algoritmo de la burbuja hay varios, con optimización y sin optimización. Concretando, yo tengo esto, por ejemplo en Java:
Código C:
Ver originalvoid ordenarBurbuja(int m[], int ne)
{
int s = 1;
int aux = 0;
int i = 0;
while ( (--ne > 0)
&& (s == 1) ) {
s = 0;
for (i = 1; i <= ne; i++) {
if (m[i-1] > m[i]) {
aux = m[i-1];
m[i-1] = m[i];
m[i] = aux;
s = 1;
}
}
}
}
Según el libro que estoy leyendo:
Cuando se analiza un método de ordenación, hay que determinar cuántas comparaciones intercambios se realizan para el caso más favorable, para el caso medio y para el caso más desfavorable.
En el método de la burbuja se realizan (n-1)(n/2) = (n^2-n)/2 comparaciones en el caso más desfavorable, donde n es el número de elementos a ordenar. Para el caso más favorable (la lista está ordenada), el número de intercambios es 0. Para el caso medio es 3(n^2-n)/4, hay tres intercambios por cada elemento desordenado. Y para el caso menos favorable, el numero de intercambios es 3(n^2-n)/2. El análisis matemático que conduce a estos valores queda fuera del propósito de este libro. El tiempo de ejecución es un múltiplo de n^2 y está directamente relacionado con el número de comparaciones y de intercambios.
En el caso mas desfavorable lo entiendo porque el primer bucle sería entero , esto es n-1 veces multiplicado por las comparaciones que se hacen el segundo que es n/2. Lo del número de intercambios de 0 lo entiendo también. Pero el n^2 que dices y el resultado para el número medio no lo acabo de entender
Gracias por la ayuda ;)
Un saludo