sort an array with minimum moves

Question

I've come across this question:

there is n+1 loading docks. a permutation of boxes 1->n is placed on the first n. there is a fork that can move one box to an empty location at a time. Give an algorithm to sort the boxes with minimum number of moves.

My algorithm (pseudo code) (1-based index)

• (0) Set counter to 0

• (1) Iterate through the array of find the max box. Move it to the last slot (n+1). increment counter by 1.

• (2) Then re-start from the beginning up to limit = n_th slot, find the max box and swap it to the end. increment counter by 3 (because a swap needs 3 moves).

• (3) Decreases limit by 1
• Go back to (2) until limit reaches 1

Updated: Saruva Sahu proposed a very nice solution below, which I optimized a tad to avoid "swapping".

  public static void moveToPos(int[] nums) {
        int tempLoc = nums.length - 1;
        final int n = nums.length - 2;
        // boxes --> loc
        Map<Integer, Integer> tracking = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            // if the target place is empty
            if (nums[i] == tempLoc) {
                // then move it there
                nums[tempLoc] = nums[i];
                // new temp loc
                tempLoc = i;

            }
            else if(nums[i] != i) {
                // move current box at target out of the way
                nums[tempLoc] = nums[nums[i]];
                if (tempLoc != nums[nums[i]]){
                    // nums[i] is not at the right place yet
                    // so keep track of it for later
                    tracking.put(nums[nums[i]], tempLoc);
                }
                nums[nums[i]] = nums[i];
                tempLoc = i;
            }
        }

        // move the unstelled to its right place
        while (!tracking.isEmpty()) {
            // where is the box that is supposed to be at tempLoc 
            int loc = tracking.remove(tempLoc);
            nums[tempLoc] = nums[loc];
            // make the emtpy spot the new temp loc
            tempLoc = loc;
        }

    }

What is the better algorithm for this?

Answer 1

Find any box that is out of place. Move it to the last dock. Then find the box that should be at the first box' original position and move it there. Then find the box for this position and so on. In the end, you will move the first box to its target position. Then, start over until all boxes are at the correct position. This will touch any box only once except the first boxes of a cycle, which will be touched twice.

Answer 2

There is a very good technique to solve this. Lets say we have boxes in this order.

[5] 4 2 3 1

Swap 1st box with 5th(which is the value of 1st box) to get:

[1] 4 2 3 5

Now 1st box is at right place. Move to second.

1 [4] 2 3 5

Swap 2nd box with 4th(which is the value of 2nd box) to get:

1 [3] 2 4 5

Now check once again if 2nd box is at right position or not. Swap 2nd box with 3rd(which is the value of 2nd box) to get:

1 [2] 3 4 5

Now check once again if 2nd box is at right position or not. If not move to the next index. Repeat above steps till the nth box.

1 2 [3] 4  5

1 2  3 [4] 5

1 2  3  4 [5]

That's it. The boxes would be sorted.

Important Points to note:

• This algorithm works only in cases when all the numbers in the array are consecutive(sorted or unsorted doesn't matter). This requirement is confirmed by the asker in comment section.
• During each swap you place at least 1 box at its correct final position, that is the best thing about this algorithm. In best cases, you may place 2 boxes in each swap as happened in first swap ([5] 4 2 3 1 -> [1] 4 2 3 5).
• Each swap would need an empty box/space which is available as per requirement.
• Each swap (between A and B) consists of 3 moves. Moving A to empty space, then moving B to A's position and then moving A back to B's old position. Consequently, A is guaranteed to get the correct final position.

Update: Algorithm suggested by Nico gives the minimum number of moves as illustrated below:

5 4 2 3 1  [ ] : Start positions
.. 4 2 3 1 [5] : 1st move
1 4 2 3 .. [5] : 2nd move
1 4 2 3 5  [ ] : 3rd move
1 .. 2 3 5 [4] : 4th move
1 2 .. 3 5 [4] : 5th move
1 2 3 .. 5 [4] : 6th move
1 2 3 4 5  [ ] : 7th move

Total 7 moves at the cost of higher time complexity O(n^2).

On the other hand, algorithm suggested by me guarantees the lowest time Complexity O(n), but NOT the minimum number of moves as shown below:

[5] 4 2 3 1  -> [1] 4 2 3 5 : 3 moves to swap 5 and 1
1 [4] 2 3 5  -> 1 [3] 2 4 5 : 3 moves to swap 4 and 3
1 [3] 2 4 5  -> 1 [2] 3 4 5 : 3 moves to swap 3 and 2

Total 9 moves at lower time complexity of O(n).

Answer 3

Example C code without swaps, using a[0] as empty slot, and assumes a[1] through a[n] have the values 1 to n in random order. Each move to a[1] to a[n] moves an element into it's final spot. The algorithm follows the "cycles" within a permutation.

int i,j,k;
    // scan a[] from 1 to n
    for(i = 1; i <= n; i++){
        if(i != a[i]){
            // if element out of place, move to a[0] 
            a[0] = a[i];
            // follow the cycle to put elements in place
            j = i;
            do{
                // find element that belongs in a[j]
                for(k = i; j != a[k]; k++);
                // move that element to a[j]
                a[j] = a[k];
                j = k;
            }while(j != a[0]);
            // move a[0] to a[j] to complete rotate of cycle
            a[j] = a[0];
        }
    }

As a more generic example, an array of indices I[] are sorted according to an array of values A[], then A[] and I[] are reordered in place according to the sorted indices in I[], with every write to A[] placing an element in it's sorted position. This is a C++ example (uses lambda compare).

int A[8] = {7,5,0,6,4,2,3,1};
size_t I[8];
size_t i, j, k;
int ta;
    // create array of indices to A[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        I[i] = i;
    // sort array of indices according to A[]
    std::sort(I, I+sizeof(A)/sizeof(A[0]),
        [&A](size_t i, size_t j){return A[i] < A[j];});
    // reorder A[] and I[] according to I[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != I[i]){
            ta = A[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                I[k] = k;
                k = j;
            }
            A[k] = ta;
            I[k] = k;
        }
    }

Answer 4

IMO, the most efficient algorithm is (if "move" means "swap", and allow move to any location):

Suppose the length of the array is n. Calculate longest increasing subsequence of the array, suppose the length of longest increasing subsequence is s, then minimal moves is n - s.

i.e.

[2, 3, 5, 4, 1], n is 5, s is 3 ([2, 3, 5]), so answer is 5 - 3 = 2

[5, 4, 2, 3, 1], n is 5, s is 2 ([2, 3]), so answer is 5 - 2 = 3