InsertSort
SRM 351 · 2007-05-29 · by Andrew_Lazarev
Problem Statement
We have an array A and we want to sort it in non-decreasing order. The only allowable operation is to move one element of the array into any other place (before all elements, after all elements or between any two adjacent elements). The cost of the single operation is equal to the value of the moved element. We want to minimize the total cost of sorting the array.
For example, we have an array {7, 1, 2, 3}. We can sort it by moving 7 from the head to the tail. But the cost of this operation is 7 which is not optimal. The optimal sorting algorithm is to consecutively move 1, 2 and 3 to the proper places before 7. The total cost of these three movements will be 1+2+3=6, which is less than 7.
You will be given a
Constraints
- theArray will contain between 1 and 50 elements, inclusive.
- Each element of theArray will be between 1 and 1000, inclusive.
{7, 1, 2, 3}
Returns: 6
The example from the problem statement.
{7, 1, 2, 5}
Returns: 7
The cheapest way to sort the array is to move 7 from the head to the tail.
{1, 8, 8, 12, 99}
Returns: 0
The array is already sorted.
{8, 2, 6, 5, 1, 4}
Returns: 18
{6, 4, 5, 3, 8, 2, 7, 2, 11, 2, 2}
Returns: 24
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class InsertSort with a public method int calcMinimalCost(vector<int> theArray) · 88 test cases · 2 s / 256 MB per case