InsertionSortCount
SRM 301 · 2006-05-09 · by soul-net
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
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.
{20,40,30,10}
Returns: 4
The example from the problem statement.
{-1,1,0}
Returns: 1
Only one move needed to insert 0.
{-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.
{1,2,3,4,5,6,7,8,9,10}
Returns: 0
{10,9,8,7,6,5,4,3,2,1}
Returns: 45
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class InsertionSortCount with a public method int countMoves(vector<int> A) · 90 test cases · 2 s / 256 MB per case