0

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.

Improve this question
12
  • 1
    Interesting problem, but somewhat under-specified, I think. For example, for physical objects, like books on a shelf, I am not convinced that remove/insert is necessarily more efficient than swap. Could you perhaps swap groups?
    – 500 - Internal Server Error
    Commented Dec 20, 2018 at 16:50
  • They are books on a shelf. Swaping in memory if efficient, in the real world not so much. But I think I found the answer to my problem. What I essentially want is a diff of the unsorted and the sorted list. @MattTimmermans gave a good answer, I'm still studying it, to see if it is easier to create my algorithm based on LCS or just use diff and work around with it. BTW: by solution described above does the same opposite of LCS (finding the odd ones out) in a small set of operations, but there is obviously room for improvement.
    – Luiz Borges
    Commented Dec 20, 2018 at 17:23
  • Have you looked at Cycle Sort where each element is either written once or zero times?
    – Blastfurnace
    Commented Dec 20, 2018 at 20:51
  • Is swap two elements one operation or two? Is this always one(two) tics, or do you want to count (and minimise) the total distance moved ?
    – wildplasser
    Commented Dec 20, 2018 at 21:20
  • You are thinking in terms of swaps, I made it clear there are NO swaps, but removals and insertions.
    – Luiz Borges
    Commented Dec 21, 2018 at 9:55

2 Answers 2

Reset to default
1

Minimizing the number of elements that are moved is the same as maximizing the number of elements that are not moved.

Since any elements you don't move will be left in their original order, those elements must be a subsequence of the desired sorted array. You can use the common algorithm to find the longest such subsequence:

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

Then remove all the elements that are not part of this subsequence, and reinsert them wherever they belong.

Note that there are optimizations you can use for this specific case of the longest monotonically increasing subsequence:

https://en.wikipedia.org/wiki/Longest_increasing_subsequence https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

Improve this answer
1
  • I think this is exactly what I need, I will read into it before marking it as answered.
    – Luiz Borges
    Commented Dec 20, 2018 at 16:53
0 
Create an integer array of size 16.  Call it fred.
Init all of the values to 0
Iterate your unsorted array.  
    use each value as a subscript into fred, setting the value to 1.

Pretend your unsorted array is empty.
Iterate fred.
    when you encounter a value of 1, that subscript needs to be inserted 
    back into your unsorted array.

Your unsorted array of size N is now sorted at a cost of N insertions
Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.