BUBBLESORT - Bubble Sort

no tags 

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

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.

Output

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.

Example

Input:
1
4
3 2 1 4

Output:
Case 1: 3

hide comments
shadan_amir1: 2019-01-01 08:48:38

This is Bill,
Bill implemented the enhanced merge sort correctly,
Bill took care of the output pattern, but
Bill forgot to write Module 10000007,
Bill got many WAs,
Don't be like Bill!!

pallav17: 2018-06-23 18:04:08

.

Last edit: 2018-07-05 12:57:47
saltyfish233: 2017-11-08 06:09:55

I did not notice ‘ needed modulo 10000007’, so I got many WAs : (

sandeep_4141: 2017-01-06 09:56:25

after getting 2 times tle ,get concept inversion count...finally do it...rock on!!

vivace: 2016-11-26 05:48:50

take care of spaces after "Case" and after ":" . Cost me 4-5 WAs.

karan_batra: 2016-08-27 11:36:55

Last edit: 2017-02-05 08:46:43
Gaurav Dahima: 2016-08-20 19:52:33

spoilers in comments :D

ov3rk1ll: 2016-06-18 07:14:46

same as invcount

Admin Deepak Baghel: 2016-06-15 20:35:26

just added single line in merge sort :)

Last edit: 2016-06-16 14:36:54
azam_9: 2016-05-25 08:33:17

absence of mod costed me 1 WA....O(nlog(n)) using modified merge sort:D


Added by:imranziad
Date:2015-11-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (H.M. Mehrab)