BUBBLESORT - Bubble Sort
题意翻译
### 题目描述
$T$组数据,每次给出长度为$N$的序列,求用冒泡排序对其排序至少需要交换几次,答案Mod10000007
**PS:以`Case t: ans`的形式依次输出,表示第$t$组数据的答案**
题目描述
One of the simplest sorting algorithms, the Bubble Sort, can be expressed as (0-based array):
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/\* if this pair is out of order \*/
if A\[i-1\] > A\[i\] then
/\* swap them and remember something changed \*/
swap( A\[i-1\], A\[i\] )
swapped = true
end if
end for
until not swapped
end procedure
Now, given an array of N integers, you have to find out how many swap opeartions occur if the Bubble Sort algorithm is used to sort the array.
输入输出格式
输入格式
Input begins with a line containing an integer **T(1<=T<=100)**, denoting the number of test cases. Then T test cases follow. Each test case begins with a line containing an integer **N(1<=N<=10000)**, denoting the number of integers in the array, followed by a line containing **N** space separated 32-bit integers.
输出格式
For each test case, output a single line in the format **Case X: Y**, where **X** denotes the test case number and **Y** denotes the number of swap operations needed modulo 10000007.
输入输出样例
输入样例 #1
1
4
3 2 1 4
输出样例 #1
Case 1: 3