Assuming an array where every element is also a positive integer number, without duplicates and without any missing elements, like the following:
{15, 1, 2, 6, 7, 8, 3, 4, 9, 5, 10, 13, 11, 12, 14}
Considering the removal and insertion (and not swaping) of each element, how can I find the most efficient move (remove/insert) operations to sort the list with the minimum number of insertions.
I think identifying individual groups is helpful since I can more easily find what needs to be moved together:
{{15}, {1, 2}, {6, 7, 8}, {3, 4}, {9}, {5}, {10}, {13}, {11, 12}, {14}}
For that I can create another array with the difference between the value and the correct position to let me easily identify the groups and which ones are furthest from being correct.
{{14}, {-1, -1}, {2, 2, 2}, {-4, -4}, {0}, {-5}, {-1}, {1}, {-2, -2}, {-1}}
Then I choosed the group furthest from being in the correct position (largest difference) and with smaller number of elements. So based on that I can see that {15} is 14 away from being correct and should be the first to be moved. I THINK (I'm guessing here) that I need to move AT least the difference in value, because I can land in the middle of group. Repeating the procedure I move the {5} to before {6,7,8}, which is moved 6 spaces, more difference between value and correct position because there is a group in its correct spot. Then {3,4}, and finally {13} and the list is sorted.
I can already create a iterative method that does just that. But I think it would be highly inefficient, since I will be dealing with about 200k values and recalculating it after every set of insertions is a terrible idea.
PS: I NEED to follow this procedure (remove and insertion of elements, and thinking in groups) instead of other more time efficient methods, since this would be applied in the real world to sort items in shelves, and something with a smaller number of operations of less items is prefered rather than computational or memory requirements.
swap two elements
one operation or two? Is this always one(two) tics, or do you want to count (and minimise) thetotal distance moved
?