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.