BUBBLESORT - Bubble Sort
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)
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
until not swapped
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.
Input: 1 4 3 2 1 4 Output: Case 1: 3
This is Bill,
I did not notice ‘ needed modulo 10000007’, so I got many WAs : (
after getting 2 times tle ,get concept inversion count...finally do it...rock on!!
take care of spaces after "Case" and after ":" . Cost me 4-5 WAs.
Last edit: 2017-02-05 08:46:43
spoilers in comments :D
same as invcount
Admin Deepak Baghel:
just added single line in merge sort :)Last edit: 2016-06-16 14:36:54
absence of mod costed me 1 WA....O(nlog(n)) using modified merge sort:D