Liczba transakcji swap w Bubble Sort

Question

Mam wersję 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]) 
    } 
} 

Chcę obliczyć oczekiwaną liczbę swapów stosując powyższą wersję bubble rodzaju. Metodę używaną przeze mnie pokazano poniżej:

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

Czy podążam właściwą drogą, czy też czegoś brakuje?

Answer 1

Najlepszym sposobem uzyskania odpowiedzi jest uruchomienie samego algorytmu sortowania bąbelkowego i uwzględnienie licznika po wywołaniu funkcji swap(). Twoja funkcja obliczeniowa będzie (a) potrzebna prawie tak długo jak sam sortowanie (w zależności od czasu działania swap() vs. getprob()) i (b) pomija punkt, w którym kolejność elementów zmienia się podczas sortowania.

Btw, dokładna liczba połączeń swap() zależy od danych, które należy posortować - masz n * (n-1)/2 porównań i każda z nich może spowodować zamianę (średnio, połowa czas wymiany porównywanych elementów).

Answer 2

Może to pomaga. Zasadniczo zapewnia to strukturę do uruchamiania sortowania bąbelkowego na zestawie zestawów danych symulacji i do obliczania prawdopodobieństwa wymiany.

Niech to prawdopodobieństwo = p Następnie, aby znaleźć oczekiwaną liczbę operacji wymiany, należy zastosować to do prawdziwego zestawu danych. Niech n będzie wielkości tego zbioru danych. Następnie oczekiwana liczba = swapProbability * n * n

n * n przychodzi, ponieważ sortowanie bąbelkowe ma liczbę n * n oczekiwanych operacji.

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