Server Time: Sat Sep 26, 2020 11:16 am
Welcome ( logout
C - Insertion sort
Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

Insertion sort is a sorting method. It is easy and better than bubble sort. The algorithm is given below:

(Insertion sort) INSERTION(A, N)

This algorithm sorts the array A with N elements.

  1. Set A[0] := -∞ {Initializes sentinel elements.]
  2. Repeat Steps 3 to 5 for K = 2,3, …. , N.
  3.   Set TEMP := A[K] and PTR := K – 1
  4.   Repeat while TEMP < A[PTR]:
    1. Set A[PTR+1] := A[PTR] [Moves elements forward.]
    2. Set PTR := PTR – 1

  [End of loop.]

  1.    Set A[PTR + 1] := TEMP. [Insets element in proper place.]

[End of Step 2 loop.]

  1. Return

 

Your task is simple. Print how many times elements move forward.

Input:

First line of input contains an integer T(T<10), denoting the test case.

Output:

For every test case, print how many times elements move forward.

 

Sample input and output:

Sample input

Sample output

2

8

77 33 44 11 88 22 66 55

5

1 2 3 4 5

Case 1: 14

Case 2: 0

 

 


Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan