CODEWITHSUNDEEP
arraysalgorithmsorting
Luiz Borges
Luiz Borges

Reputation: 567

Minimize number of insertions when sorting an array

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.

Upvotes: 1

Views: 303

Answers (2)

EvilTeach
EvilTeach

Reputation: 28837

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

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59184

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/

Upvotes: 2

Related Questions