Block Sorting
Suppose that someone gives you a list of items that are "partially sorted,"
such as
this.
You need to sort them, but you want to move as few "blocks" as possible.
Each move consists of moving a contiguous block of items.
For example, one move from the previous list gives you
this,
and one more move gives you the
sorted list.
That's two moves.
Write an algorithm that finds the fewest number of block moves needed to
sort a given list.
We can make this a 0/1 question by asking, "Given a certain list L and
an integer k, can L be sorted in at most k block moves?"
This is a very simple problem. Or, is it?