Numero di swap in Bubble Sort

Question

Ho una versione di bubble sort:

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

voglio calcolare il numero previsto di swap che utilizzano la versione sopra di bubble sort. Il metodo utilizzato da me è mostrato di seguito:

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

Sto andando nel modo corretto o mi manca qualcosa?

Answer 1

Il modo migliore per ottenere la risposta è eseguendo l'algoritmo di ordinamento delle bolle stesso e includendo un contatore dopo la chiamata di swap(). La tua funzione di calcolo avrebbe (a) bisogno di un tempo pari a quello del sort stesso (a seconda del tempo di esecuzione di swap() e di getprob()) e (b) manca il punto in cui l'ordine degli elementi cambia durante l'ordinamento.

Btw, il numero esatto di chiamate swap() dipende dai dati che è necessario ordinare - si hanno n * (n-1)/2 comparazioni e ognuno di essi potrebbe comportare uno swap (in media, metà di il tempo necessario per scambiare gli elementi confrontati).

Answer 2

Forse questo aiuta. Fondamentalmente questo fornisce un framework per eseguire sort bubble su un set di set di dati di simulazione e calcolare la probabilità di swap.

Lasciare questa probabilità = p Quindi per trovare il numero previsto di operazioni di scambio, è necessario applicarlo su un set di dati reale. Sia n la dimensione di questo set di dati. Poi previsto numero = swapProbability * n * n

n * n deriva dal fatto che l'ordinamento di bolle ha n * n numero di operazioni previste.

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);