Server Time: Sat Feb 22, 2020 9:49 am
 Welcome ( logout )
C - Insertion sort
 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

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