Número de trocas no Bubble Sort
Eu tenho uma versão do 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])
}
}
Eu quero calcular o número esperado de swaps usando a versão acima do bubble sort. O método usado por mim é mostrado abaixo:
// 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].
}
}
Eu estou indo da maneira correta ou estou faltando alguma coisa?