Geek asks and answers

Number of swaps in Bubble Sort

I have a version for sorting bubbles:

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]) 
    } 
}

I want to calculate the expected number of swaps using the above version of the bubble sort. The method I use is shown below:

// 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].
    }
}

Am I going the right way or am I missing something?

+5
source share
3 answers

The best way to get the answer is to run the bubble sorting algorithm itself and turn on the counter after calling swap (). Your calculation function will (a) need almost as much as the sort itself (depending on the execution time of swap () and getprob ()) and (b) skip the point when the order of the elements changes during sorting.

Btw, swap() , - n * (n-1)/2 , ( , , ).

+5

, . .

= p , , . n - . = swapProbability * n * n

n * n , n * n .

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;
}
+2
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);
0
source

More articles:


All Articles