Ordenación método de la burbuja

[neveldinered]

Hola,

Por qué en el caso medio tenemos 3(n^2-n)/4 comparaciones. Entiendo que viene de (n-1)/2 * (3/2)*n
Pero no entiendo por qué el (3/2) * n. ¿Es decir, por qué hay 3 intercambios por cada elemento desordenado?

Gracias anticipadas.

Un cordial saludo

[eferion]

El caso más desfavorable implica A=(n^2-n)/2 comparaciones.
El caso más favorable, B=n^2.
El término medio, dado que se supone un sistema uniformemente distribuido, serán (A+B)/2=(n^2+(n^2-n)/2)/2=(3n^2-n)/4 comparaciones.

No se de donde sacas lo de los 3 intercambios... Estas hablando de un término medio (que no trata de ningún caso en concreto) y además, esta fórmula únicamente habla de comparaciones, no de intercambios.

Es decir, si inicializas una lista con valores aleatorios, la ordenas y contabillizas las comparaciones realizadas y repites el proceso durante muchas veces, el valor medio tenderá a parecerse al de la fórmula que comentas.

Un saludo

[pyromiyuve]

Exacto, pero si todavia tienes dudas prueba ejemplos con el codigo y asi refuerzas la teoria.

Código C++:

long double Cont;
 
void ordenarBurbuja(int A[], int n)
/* A[]= vector a ordenar
   n= tamaño del vector
*/
{
    int i=0, j=0;
    int aux;
    for (i=1; i<n; i++)
    {
        Cont++;
        for(j=0; j<n-i; j++)
        {
            Cont++;
            if (A[j]>A[j+1])
            {
                aux=A[j];
                A[j]=A[j+1];
                A[j+1]=aux;
            }
        }
    }
}
 

[neveldinered]

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:

void 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

[eferion]

Piensa que estas hablando de comparaciones no se sustituciones. Si has visto como funciona el algoritmo entenderás que hay que hacer un número mínimo de comparaciones para asegura que la lista esta ordenada y eso es independiente de lo optimizado que este el algoritmo... Si consigues que el caso óptimo realice un número menor de comparaciones es porque estas usando otro algoritmo.