March 2001 Programmer's Challenge

DragSort

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Thursday, 1 March 2001

I’ll confess. I’ve done it. More than once, actually. It’s probably not legal, strictly speaking. But how bad can it be. I mean, lots of people must do it. It’s not something truly evil like, well, like Napster.

What am I talking about? Downloading music. From the internet. Music that other people posted, music that I haven’t purchased. Yet, that is. Music posted to the UseNet alt.binaries.sounds.* newsgroups.

What does this have to do with the Programmer’s Challenge? Downloading Usenet binaries is a (perhaps contrived) motivation for this month’s problem, that of sorting a list of items in a particular way. Large binaries are posted in a sequence of parts, and newsreaders thread the parts based on sequence information included by convention in the subject line. But sometimes the subject line contains information that confuses the sequencing, meaning that the parts need to be sorted manually before the binary information can be extracted. With the newsreader I use, the parts are sorted by dragging items from one position in the list to another position, until the parts appear in the correct order.

Your Challenge is to find an efficient way to perform this sort. Efficient in this case means minimizing the amount of tiresome clicking and dragging needed to put the parts in the correct order. Specifically, you want to minimize the cumulative number of positions that you need to move to select the part to be dragged, and the number of positions you need to drag the parts. An example in a later paragraph will make this a little clearer.

Oh, and before you turn me in to the authorities, downloading music from the internet allows one to sample the music before deciding whether to buy it. We all, of course, buy what we keep.

The prototype for the code you should write is:

typedef struct Move {   /* describes moves used to sort itemsToSort */
 long selectPosition;   /* select this item in the array, origin 0 */
 long dragToPosition;   /* drag selected item to this position in the array, origin 0 */
} Move;

long /* numMoves */ DragSort(
 long itemsToSort[],   /* array of items to be sorted */
 long numItemsToSort,  /* number of itemsToSort */
 long startPosition,   /* item initially selected */
 Move sortMoves[]      /* store Moves that sort the array here */
);

Your DragSort routine will be called with a list of itemsToSort, a count of the number of items in the list (numItemsToSort), and the element of the list initially selected (selectPosition). DragSort should calculate a sequence of Moves that reorder the list into ascending order by moving the item located at one position in the list (selectPosition) to another position in the list (dragToPosition). Moves are returned in the sortMoves array, and the number of Moves needed to sort the array should be returned by DragSort.

Sounds simple and boring, right? The catch is in how your sort solution is scored. You are penalized one point for each position move your solution makes while performing the sort — one point for each position between your current location and the selectPosition of the next Move, and one point for each position between that selectPosition and the dragToPosition. When a Move is completed, your current position is the dragToPosition. The penalty for the next Move is the number of positions between the previous dragToPosition and the current selectPosition, plus the distance from the current selectPosition and the current dragToPosition, etc.

Imagine, for example, that you are asked to sort the following list, with a startPosition of 0:

       6 1 2 3 5 4

You might employ a bubble sort. Your first Move is to select the 2^nd item in the list and move it to the 1^st position, at a cost of two penalty points (moving from [0] to [1], and dragging from [1] to [0]). The list now looks like this:
       1 6 2 3 5 4

Next you might move the 3^rd item to the 2^nd position, at a cost of 3 penalty points (moving from [0] to [2], and dragging from [2] to [1]), leaving the list like this:
       1 2 6 3 5 4

Then you might move the 4^th item to the 3^rd position, at a cost of 3 more penalty points. Then the 6^th item to the 4^th position (cost 5 points), and the 6^th item to the 5^th position (cost 3 points). The list would then be correctly sorted, at a cost, if I have counted correctly, of 16 points.

And you would lose the Challenge.

A more successful contestant would sort the list at a cost of 7 points as follows:
       6 1 2 3 5 4
       1 2 3 5 4 6 (cost 5 points)
       1 2 3 4 5 6 (cost 2 points)

In addition to the points incurred for dragging list items around, a penalty of 1 point will be assessed for each millisecond of execution time. The winner will be the entry that correctly sorts a sequence of lists while accumulating the fewest penalty points. The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.