Algorithm for generating sorting instructions

Generally speaking, you sorting algorithm should involve the following two steps:

1. Sort the books and assign them a numerical order.
2. Generate optimal sorting instructions given the permutation.

In your example, you start with a list of four books. Sorting them, you assign them a numerical order, B C A D (the numbers here are A,B,C,D). Then you figure out instructions for sorting the permutation B C A D. One approach that will always work is to move A to 0, B to 1, C to 2, and so on. However, this is not optimal. Figuring out the optimal sequence of moves seems like the difficult part of your question.

You seem to think that you problem is well stated, but I have some doubts.

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 computed).

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 complete disorder.

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. https://cstheory.stackexchange.com/questions/4096/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 using.

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 the abstraction.

Since you didn't ask for the minimal amount of book moves but just the sequence, here's a way that will always work.

Initial work. For each book, count the number of books to its left whose titles are alphabetically after its title. Arrange these numbers in a list, starting with the earliest in order. For example, if the initial arrangement was CFABDE, your list will be 2, 2, 0, 1, 1, 0, since

1. Book A had C and F to its left, so the first entry in the list would be 2.
2. Book B had C, F, A to its left, and C and F were alphabetically after B, so the second entry in the list would be 2.
3. Book C had nothing to its left, so the third entry would be 0.
4. Book D had C, F, A, B to its left and F is alphabetically after D, so the fourth entry would be 1.
5. Similarly, book E had C, F, A, B, D to its left, so the fifth entry would be 1.
6. Finally, the sixth entry, for book F, is obviously 0.

In technical terms, you've produced an inversion sequence for the permutation CFABDE: $$\begin{array}{lcccccc} \text{Index:} & 0 & 1 & 2 & 3 & 4 & 5 \\ \text{Entry:} & 2 & 2 & 0 & 1 & 1 & 0 \end{array}$$

Producing the move sequence. We'll produce a list of instructions that will sort this initial sequence by repeatedly swapping adjacent books. I'll denote the swap of books in positions $i$ and $i-1$ by the instruction $(i, i-1)$. For every book $i$, in alphabetic order, swap book $i$ with its $b_i$ left neighbors, starting at the right.

For our example, we'll have the following operations:

1. Book A ($i=0$, currently in position 2): $b_0 = 2$ so we'll swap book A with its two left neighbors, F and C, in that order: CFABDE $\rightarrow$ CAFBDE $\rightarrow$ ACFBDE, so the first two instructions are $(2, 1), (1, 0)$.
2. Book B ($i=1$, currently in position 3): $b_1 = 2$ so we'll swap book B with its two left neighbors, F and C, in that order: ACFBDE $\rightarrow$ ACBFDE $\rightarrow$ ABCFDE, so the next instructions are $(3, 2), (2, 1)$.
3. Book C ($i=2$, currently in position 2): $b_2 = 0$ so make no swaps.
4. Book D ($i=3$, currently in position 4): $b_3 = 1$ so we'll swap book D with its left neighbor, F: ABCFDE $\rightarrow$ ABCDFE, giving the instruction $(4, 3)$.
5. Book E ($i=4$, currently in position 5): $b_4 = 1$ so we'll swap book E with its left neighbor, F: ABCDFE $\rightarrow$ ABCDEF, giving the instruction $(5, 4)$.
6. Book F: the last book will always be in its correct position, so we make no swaps.

Finally, we can sort these books by the instructions $(2, 1), (1, 0), (3, 2), (2, 1), (4, 3), (5, 4)$, in that order.

It should be noted that this method won't necessarily produce a minimal-length instruction sequence, but it eliminates the problem you noted of having to keep track of the intermediate rearrangements and it also eliminates some of babou's real-world problems, since you're only swapping adjacent books. It seems at first to be complicated, but I'd guarantee that after the tenth book it would be completely automatic.