Bubble Sort
Description
Bubble sort is one of the simplest sorting algorithms. It works by repeatedly iterating thru the array to be sorted, comparing two adjacent numbers in the array, and swapping them if they are in the wrong order. The iterations thru the list are repeated until no swaps are needed, which means that the array is sorted. The code below will show you how bubble sort works:
void BubbleSort(Vector a, int n)
{
for(int j=n-1; j > 0; j--)
for(int k=0; k < j; k++)
if (a[k+1] < a[k])
Swap(a,k,k+1);
}
As a programmer, we are concerned about the expected number of swaps and how much would the swapping number change when the given vector is randomly ordered. For such purpose, let us consider the general problem.
Suppose that is a permutation of n numbers, drawn uniformly at random from the set of all n! permutations. Let X be the random variable which counts the number of inversions of , i.e., the number of pairs of indices i < j such that (i) > (j).We want you to determine expectation E[X] and variance Var[X]. Suppose X is a random variable, it can takes value xi(i=1,2,…,n) and the probability it takes value xi is Pr(xi).E[X] and Var[X] are two important statistics in probability theory, their formulas are given below:
Input
He first line of the input contains the number k, the number of test cases to solve (1 ≤ k ≤ 200). Each test case consists of a single integer 2 ≤ n ≤ 1000 on a separate line.
Output
For each case, you should output the expectation E[X] and variance Var[X], which are separated by a blank space, on a line. You need to output the answer to 2 decimal places.
Samples