TopCoder problem "InsertionSortCount" used in SRM 301 (Division II Level One)



Problem Statement

    

A sequence of distinct numbers A is going to be sorted using insertion sort. Insertion sort works as follows:

insertion-sort(A)
   initialize a new empty sequence R
   for each number N in A (in the original order) do:
      determine the index i in R where N should be inserted so that R remains sorted
      move each element in R with index greater than or equal to i to the following index
      set R[i]=N
   return R

For example, an insertion sort on {20,40,30,10} would produce the following states for R after each step:

20 (first element is inserted at index 0)

20,40 (inserting 40 at index 1 requires no moves)

20,30,40 (30 is inserted at index 1, so 40 has to be moved)

10,20,30,40 (10 is inserted at index 0, so 20, 30 and 40 have to be moved)

In total, 4 moves were needed.

Given a int[] A, which contains a sequence of distinct numbers, return the number of moves that would be performed by an insertion sort on A.

 

Definition

    
Class:InsertionSortCount
Method:countMoves
Parameters:int[]
Returns:int
Method signature:int countMoves(int[] A)
(be sure your method is public)
    
 

Constraints

-A will have between 1 and 50 elements, inclusive.
-Each element of A will be between -1000 and 1000, inclusive.
-All elements of A will be distinct.
 

Examples

0)
    
{20,40,30,10}
Returns: 4
The example from the problem statement.
1)
    
{-1,1,0}
Returns: 1
Only one move needed to insert 0.
2)
    
{-1000,0,1000}
Returns: 0
Since elements are inserted in sorted order, all of them are appended at the end of R. Therefore, there's no need to move anything.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6224

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9822&pm=6224

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Simple Search, Iteration, Sorting