c++ - bubble sort pseudocode

Número de swaps en Bubble Sort

Question

Tengo una versión de tipo burbuja:

int i, j;  

for i from n downto 1 
{
    for j from 1 to i-1 
    { 
        if (A[j] > A[j+1])
            swap(A[j], A[j+1]) 
    } 
}

Quiero calcular el número esperado de intercambios usando la versión anterior de sorting de burbuja. El método utilizado por mí se muestra a continuación:

// 0 based index

float ans = 0.0;

for ( int i = 0; i < n-1; i++ )
{
    for ( int j = i+1; j < n; j++ ) {

        ans += getprob( a[i], a[j]); // computes probability that a[i]>a[j].
    }
}

¿Estoy yendo de la manera correcta o me estoy perdiendo algo?

Answer 1

La mejor forma de obtener la respuesta es ejecutando el algoritmo de ordenación de burbujas e incluyendo un contador después de la llamada swap (). Su función de cálculo (a) necesitaría casi tanto como el género en sí (dependiendo del tiempo de ejecución de swap () frente a getprob ()) y (b) omitir el punto en que el orden de los elementos cambia al ordenar.

Por cierto, el número exacto de llamadas swap () depende de los datos que necesita ordenar, tiene n * (n-1) / 2 comparaciones y cualquiera de ellas podría resultar en un intercambio (en promedio, la mitad del tiempo que necesita para intercambiar los elementos comparados).

Answer 2

Tal vez esto ayude. Básicamente, esto proporciona un marco para ejecutar clases de burbuja en un conjunto de conjuntos de datos de simulación y calcular la probabilidad de intercambio.

Deje esta probabilidad = p Entonces para encontrar el número esperado de operaciones de intercambio, necesita aplicar esto en un conjunto de datos real. Deje n ser el tamaño de este conjunto de datos. Entonces número esperado = swapProbability * n * n

n * n viene porque la clase de burbuja tiene n * n número de operaciones esperadas.

float computeSwapProbability()
{
    int aNumSwaps = 0
    int aTotalNumberOfOperations = 0

    For all simulation datasets
    {


        int i, j;  

        for i from n downto 1 

        { 

            for j from 1 to i-1 

            { 
                aTotalNumberOfOperations++

                if (A[j] > A[j+1]) 
                {
                    swap(A[j], A[j+1]) 
                    aNumSwaps++
                }

            } 

        }
    }

    return (float)aNumSwaps/aTotalNumberOfOperations;
}

Answer 3

The best way to count swap is to include counter variable inside swap if condition .

    int swapCount=0;

    for (i = 0; i < (length-1); ++i) {
      for (j = 0; j < (length-i-1); ++j) {
        if(array[j] > array[j+1]) {
          temp = array[j+1];
          array[j+1] = array[j];
          array[j] = temp;
          swapCount++;
        }
      }
    }

    printf("Swap count : %d" ,swapCount);