Sorting by moving groups of numbers

[Borek]

It all starts with a shuffling. We have a sorted list, we take out groups of numbers and we insert them in random positions:

Then, it is about sorting the numbers back using the same approach, in a minimum numbers of steps (which doesn't have to be identical to a number of steps taken during shuffling, but as we shuffled this way it is guaranteed that the process can be reversed).

Actually I don't care about how to find the solution. My question is - is it a known problem? Something that you can easily google if you know the name or correct keywords? Apparently I don't know them, but I have never studied CS and my English is limited, so chances are I am missing something obvious.

It is one of possible problems for a competition and I don't want to use something that people will know how to solve right away.

 

[jedishrfu]

The nearest I can think of is a merge sort that works something like solitaire.

https://en.wikipedia.org/wiki/Merge_sort

 

[Silicon Waffle]

From what you describe, I think there are many problems related to this sort of "group movement". From what I have always been inspired to learn, this looks like part of phylogenetic tree or genomic reconstruction at a more difficult level if some or many of the numbers are lost and we thus need to find approximate ones to fill up the empty places. So people may use something as simple as what you describe here to model such a big picture of reconstruction. Algorithmic approaches to looking up the original sequence of numbers are also challenges to computer scientists.

 

[QuantumQuest]

I have not heard of this as a specific problem in the CS courses I've attended so far, but I think is nothing more than random partitioning and shuffling. Now, for the sorting process after that, if you don't follow the same path you followed initially, then you have to somehow compare and sort the partition numbers inside partitions and between them in order to reach a sorted state. If the list is sufficiently large, then - if you don't reach a sorted state randomly before doing anything to sort it., you'll have to follow costly operations and so not efficient. It would be much easier given any state you reached after random partitioning and shuffling, to use an efficient sorting algorithm ( modified quick sort or merge sort for instance) to do the job but this violates the constraints you refer. So, you probably have to resort on the reverse process.

 

[newjerseyrunner]

Sounds like a block sort.

 

[bigfooted]

if you move blocks around often enough, the array becomes completely unsorted and knowledge of your shuffling process will not help, but for partially ordered lists you can gain some time by looking for ordered sequences. This is implemented in Timsort:
https://en.wikipedia.org/wiki/Timsort
In your case, if you start by looking for an ordered sequence containing the largest values, you will find {8,9} and move it to the end, effectively moving {6,1,2,7} to its previous position. If you again look for an unsorted ordered sequence with the largest values, you will find {3,4,5,6}

timsort looks for ordered subarrays so it will find {0,3,4,5,8,9} and {1,2}. I think it will then also recognize that {6,7} is an ordered sequence.
It will then merge the three ordered arrays.

You can maybe modify this algorithm to use subarrays of size 4 so it mimicks you shuffling method.

 

[Borek]

You can maybe modify this algorithm to use subarrays of size 4 so it mimicks you shuffling method.

Actually there is no limit on the size of the packet moved, it was accidental (and an overlook) that I painted them in fours.

Thank you all for your insight so far, at least it looks like it is not something entirely obvious. Similar to known problems, but different enough.