CODESPTB - Insertion Sort
Insertion Sort is a classical sorting technique. One variant of insertion sort works as follows when sorting an array a[1..N] in non-descending order:
for i <- 2 to N j <- i while j > 1 and a[j] < a[j - 1] swap a[j] and a[j - 1] j <- j - 1
The pseudocode is simple to follow. In the ith step, element a[i] is inserted in the sorted sequence a[1..i - 1]. This is done by moving a[i] backward by swapping it with the previous element until it ends up in it's right position.
As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.
Input
The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1], a[2] ... a[N].
Output
Output T lines, containing the required answer for each test case.
Constraints
1 ≤ T ≤ 5
1 ≤ N ≤ 100000
1 ≤ a[i] ≤ 1000000
Example
Sample Input: 2 5 1 1 1 2 2 5 2 1 3 1 2 Sample Output: 0 4
hide comments
daltroov777:
2023-04-23 15:21:31
What is BIT? |
|
tarun_28:
2020-08-28 20:22:28
Same as INVCNT;) |
|
thanos_tapras:
2020-03-25 17:28:21
Nice problem with basic implementation and bit |
|
purplecs:
2019-11-15 14:13:53
easy.just apply BIT |
|
krish1997:
2019-06-21 11:18:00
Basic insertion sort with counter at each swap works. |
|
the_ashutosh:
2019-03-08 07:47:01
just count the inversions in the array.....using bit or segment tree |
|
karan_yadav:
2018-07-17 07:28:17
This question screams merge sort tree, though you don't have to create the whole tree. Just sorting would do.
|
|
karthik1997:
2017-12-27 16:47:21
BIT was much faster than mergesort trick , and be careful with \n at the end. it costed me many WA's :) |
|
ANKIT JAIN:
2017-05-06 12:16:07
Solved using BIT :) |
|
vaibhavk31:
2017-03-31 14:54:30
Test cases are weak
|
Added by: | Varun Jalan |
Date: | 2011-10-15 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem used for CodeSprint - InterviewStreet Contest |