You seem to think that you problem is well stated, but I have some
Nothing is obvious, unless properly defined. When you move
0 -> 2,
what happens to book 2, is it out, or does it stay next to book formerly 0,
probably behind it, in position behind the book formerly 0 you just moved (which happens to still be 2 in this case). It is for you to specify that precisely.
I am here assuming that book 0 is placed before book 2, thus becoming
book 1, since book 1 becomes book 0.
Then you could use other elementary steps, such as swapping two
adjacent books, or more likely transposing two distant books, which is
often easier than moving a single one, which may have to go on a shelf
that is already full. That may however depend on whether books have
the same thickness. Even if the shelf is not full, it is more costly
to insert a book at the beginning than at the end of the shelf, since
you have to move part of the row to make place for the inserted
book. There are probably other considerations of the same kind, so
that your one step instruction is by no means a constant cost
operation in the real world, as it may seem on the computer. Now, it
may be possible to consider an average cost (that depends on shelves
fullness and possibly on the size of the collection), but that
requires careful analysis.
Another problen is that identifying the book with index $i$ is by no
means a simple operation in the real world, since your indexes keep
changing. So the books cannot carry the index, and you have to count.
Now, it is possible to force counting only on one shelf, if you keep
track of shelves content in your algorithm. But that may require that
the program knows about book thickness, and also instructs you
regarding moving the end of a shelf to another shelf. Indexing is a
unit operation on the RAM computer, but may not be in the real world.
Actually, your shelves are more like a Turing machine tape.
Then, as already answered by Yuval Filmus, the actual sorting
algorithm does not matter, since the cost of computing the final order
of books on a computer is irrelevant. You are not concerned at all
with testing relative order of books, but only in producing a minimal
sequence of moves to get from one permutation (the initial order on
the shelves) to another permutation (the sorted order that you have
I do not know what could be the best algorithms to to that.
However, given the cost of indexing and of moving a single book, I
would not proceed with the type of instructions you suggest. What may
be the right procedure is probably dependent on the density of books to
be moved, i.e. on whether the collection is nearly sorted, or in
If your basic instruction was a book transposition (exchange of two
distant books), then the is some literature on this. See for example Minimum number of transpositions to sort a list.
However, I doubt this literature takes into account the practical
problems I describe above.
Also, I do not know where to look for the kind of instructions you are
The major costs that I see come more from making room for the books
and indexing, and I would rather worry about a physical organization
to minimize these costs.
If the density of out-of-order books is low. One possibility would be
to extract them, sort them, and merge them back on the shelves. But
that is far from the initial problem.
If your question was merely a way to illustrate an bastract problem, you
should be more explicit about it, as the reality distorts considerably