Sort With A Cost

Swapping costs us $(i-j)^2$ , can we do better? Suppose that we want to swap x and y in the list x 0 0 y . We can actually do so by swapping y to the left 3 times, and then x to the right 2 times. See the illustration below :

1
2
3
4
5
6

x 0 0 y
x 0 y 0
x y 0 0
y x 0 0
y 0 x 0
y 0 0 x

This will only costs 5 which is smaller than 9 of that we use the given swap operation. In general, swapping indices $i$ and $j$ only costs us $2|i-j|-1$ .

The much cheaper costs operation is due to the "shifting" of numbers. From now on we shall use shifting instead of swapping because it performs better and gives us more flexibility (ie. when you only want to move the number to a position without affecting the order of other numbers). Since swapping a number to the left is the same as swapping the left of that number to the right, we can confidently say that we only need to perform shifting to one of the direction, we use left in this solution.

When the number can only shift to the left, we definitely don't want to shift over a number that is smaller than it because in the future we will need that smaller number to shift left again to get back to its correct position. Furthermore, if the number on the left is greater, shift over it is inevitable. Hence, each time we find the smallest number in the unsorted array, and shift it to the left until its correct position. Perform this until the array is sorted. See the illustration below on how to use only 4 shifts to sort the array 4 1 3 2 :

1
2
3
4
5

4 1 3 2
1 4 3 2
1 4 2 3
1 2 4 3
1 2 3 4

C++ program

 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
35
36
37
38

#include <bits/stdc++.h>
using namespace std;

int a[1000], b[1000];

int main() {

    int N = 5;

    for (int i = 0; i < N; i++) {
        scanf("%d",&a[i]); b[i] = a[i];
    }

    sort(b,b+N);

    int count = 0;

    for (int i = 0; i < N; i++) {
        int num = b[i];

        int whr = 0;
        for (int j = 0; j < N; j++) {
            if (a[j] == num) {
                whr = j;
            }
        }

        while (whr > 0 && a[whr] < a[whr-1]) {
            swap(a[whr],a[whr-1]);
            whr = whr - 1;
            count++;
        }
    }

    cout << count << endl;

    return 0;
}     

Not an optimal code since there are only 900 numbers in the array.

Interesting problem I did the code in C# in a similar way.

I would like to point out that that I think, in a way, Chris was lucky or perhaps intuitively noticed that the original sequence of numbers in the list was a bit closer to being in ascending order than descending order. If by chance the original sequence of numbers was closer to a descending order than it would have paid off to load the list last first and sort from there. That is easily done by loading the first integer in the list into the last position in an array and carry on reading into the array until the first indices contains the last integer in the list. Then the same process used on the original sequence would be used to sort the array into ascending order from that new starting order.

As it happens with this given list, the cost to sort into ascending order from that reverse starting position (last element first). would be 203316. Since that cost is greater then the cost to sort starting the sequence with the first element of the list in the first position of the array (as was done here) the answer 201234 is correct. I believe there is a 50% chance that starting from the other end may result in a more effective sort because it would involve less swaps. I don't know of any absolute positive way to determine which direction to sort without trying both and determining which starting point sequence would result in the fewest number of swaps. Sorting the list from both directions would result in more then twice as many sorts at more than twice the cost. I believe we have a 50% change of getting this problem correct with only one sort.

example list to sort

4312 will require many swaps to arrive at 1234

but when we read the list in backward we get 2134

2134 list requires only one swap to arrive at 1234

using the array sequence from the above solution as another example

4 1 3 2 is the array sequence that is used as an example

2 3 1 4 Is that sequence load in reverse order

2 1 3 4

1 2 3 4 only 2 shifts required in this sort compared to 3 shifts in the original sort.

I believe, that there would be no where near the same number of swaps required when sorting a list that was already near an ascending or descending order if that list was sorted from the original sequence or the reverse sequence starting point.