Lily's Homework · Coding Gym

Solutions

The sum is minimal when the array is sorted. Both descending and ascending order will yield the minimum sum of the absolute difference of adjacent elements. We need to count the number of swaps in both cases.

To find the number of swaps we have to find the number of cycles in the array. For instance, given the following array:

1

1  2  4  3

We can construct a directed graph by making each value of the array point to its sorted position:

\(1 \rightarrow 1\)
\(2 \rightarrow 2\)
\(4 \rightarrow 3\)
\(3 \rightarrow 4\)

Visually:

Other examples:

Intuitively, a cycle is a directed path that starts and finishes on the same value. The length of a cycle is the number of arrows the cycle is made from.

You can see that given a cycle of length \(l\), making all its values reach their correct order require \(l-1\) swaps. Try that yourself.

Thus, the total number of swaps required to sort the array is given by summing up all the cycle “resolutions”.

One possible solution to the original problem consists in calculating the number of swaps for both the array and the reversed array, and then returning the minimum value between the two.

A map is used as a support data structure. Alternatively, an array of pairs is very common in this kind of problems (left as an exercise).

Roughly, the idea consists in sorting a copy of input array and filling up the map with the input element positions.

Then we compare each element of the input array with the sorted array. If any mismatch is found, we have to swap the element out of position with the “expected” one.

For example:

1

1 2 4 3

1 and 2 are found in their final position. Instead, 4 is not and then it gets swapped with 3.

The position table is updated as well, just by changing the position of the element out of order to the expected element position.

In the example above, the position table is initialized as follows:

1
2
3
4


1 -> 0
2 -> 1
3 -> 3
4 -> 2

When 4 and 3 are swapped, the position of 4 is set to 3.

Another example:

1

2 5 3 1

The position table:

1
2
3
4


1 -> 3
2 -> 0
3 -> 2
5 -> 1

The first iteration finds that 2 is out of order. It gets swapped with 1 and the position of 2 is updated. So we have:

1

1 5 3 2

And the position table:

1
2
3
4


1 -> 3 (not used anymore)
2 -> 3
3 -> 2
5 -> 1

The second iteration find that 5 is out of order and it gets swapped with 2 (found thanks to having updated the position table before):

1

1 2 3 5

And the position table:

1
2
3
4


1 -> 3 (not used anymore)
2 -> 3 (not used anymore)
3 -> 2
5 -> 3

In the third and fourth iterations, the algorithm does nothing.

At the end of the main loop, we have an interesting side effect: each element position is the last one of its cycle, this makes a sort of “grouping by cycle”.

Here is a possible C++ implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


int swaps(vector<int>& v)
{
    auto sorted = v; 
    sort(begin(sorted), end(sorted));
    auto n = v.size();
    
    map<int, int> m;
    for (auto i=0u; i<n; ++i)
        m[v[i]] = i;
    
    auto swaps = 0;
    for (auto i=0u; i<n; ++i)
    {
        auto expected = sorted[i]; // we expect this element to be here
        if (expected != v[i])
        {
            swaps++;
            auto expectedPos = m[expected]; // real position of the expected element
            m[v[i]] = expectedPos; // update the position of the element out of order
            swap(v[i], v[expectedPos]); // fix, at least, the expected element position
        }
    }
    
    return swaps;
}

int main()
{
    int n; cin >> n;
    vector<int> v(n);
    copy_n(istream_iterator<int>(cin), n, begin(v));
    vector<int> reversed(rbegin(v), rend(v));
    cout << min(swaps(v), swaps(reversed));
}

The cost is, clearly, \(O(N \cdot logN)\).

Andrea Battistello and Gabriele Russo implemented the “dual” approach by storing positions of the sorted array instead:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


def lilys_homework(arr):
    sorted_arr = sorted(arr)
    arr = [x for x in arr]  # Make a copy

    idxs_ = {x : i for i,x in enumerate(sorted_arr)}
    count = 0
    i = 0
    while i < len(sorted_arr):
        if arr[i] == sorted_arr[i]:
            i+=1
            continue
        
        count += 1
        idx = idxs_[arr[i]]

        arr[i], arr[idx] = arr[idx], arr[i]
        
    return count

Note that another working solution consists in simulating the selection sort by finding the minimum element on every iteration and performing the proper swap. This solution works on all test cases, even though it’s quadratic. Indeed, the selection sort is the sorting algorithm that ensures the minimum number of swaps. Intuitively, during each iteration, the selection sort swaps the minimum element with the element in its final position. Then, the “window” of elements to be sorted gets smaller by one. This means, each element has the opportunity be the minimum only once, thus no element can be swapped more than once.

sort