Pickett,

I apologize for the hasty wording in my previous post. Of course, a computer program takes a measurable number of "steps" - once you define the term "step." You could count at the binary level, you could count the number of times you read or write a value, you could count the number of times you iterate through a specific loop, you could count the levels of recursion of achieved by a specific function, or you could count something slightly more arbitrary, such as the number of times you move an entry to another place in the list and then shift everything over. My post was in response to a post that suggested that we looked at the several sorting algorithms (including insertion sort, bubble sort, merge sort, shell sort, and quicksort), and there was a link to a website comparing the running times of these algorithms. I was simply saying that we would have to look at the number of "steps" made rather than at the running times, but that a "step" would be difficult to define in many of these sorting algorithms, especially since in some of these algorithms work by repeating a basic action that does not fulfill the requirements for a valid "step" as described in the OP. One example would be mergesort, which divides the set into two sublists, recursively applies mergesort on them, and them merges them together by repeatedly comparing the two lowest elements (one from each sublist) and then moving the lower element back onto the original list.

Also, as I understand it, the OP does not specify an algorithm for sorting the DVDs. It must just be assumed that the individual somehow makes the fewest number of moves before achieving order (or if it helps to think of it this way, the best algorithm for any arrangement rather than the same algorithm for all). We can ask BMAD to clear this up, but even if it is wrong, my interpretation would also make a pretty interesting problem.

If we follow your algorithm (as I understand it), then with the following arrangement of 11 DVDs:

BADCFKEHGJI

ABDCFKEHGJI (move A to the first position)

ABCDFKEHGJI (move C to the third position)

ABCDEFKHGJI (move E to the fifth position)

ABCDEFGKHJI (move G to the seventh position)

ABCDEFGHKJI (move H to the eight position)

ABCDEFGHIKJ (move I to the ninth position)

ABCDEFGHIJK (move J to the tenth position)

We make 7 moves. However, there is a simpler solution:

BADCFKEHGJI

ABDCFKEHGJI (move B to before A)

ABCDFKEHGJI (move C to before D)

ABCDEFKHGJI (move E to before F)

ABCDEFKGHJI (move G to before H)

ABCDEFKGHIJ (move I to before J)

ABCDEFGHIJK (move K to the end)

This only takes 6 moves, and I would say that it cannot take less then 6, regardless of what sequence of moves we make or what algorithm we follow. However, I have no proof, and I think that is the problem.

**Edited by gavinksong, 26 July 2013 - 07:34 AM.**