Mar 01 Challenge
Volume Number: 17
Issue Number: 3
Column Tag: Programmer's Challenge
Programmer's Challenge
By Bob Boonstra, Westford, MA
DragSort
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 */
long /* numMoves */ DragSort(
long itemsToSort[], [TOKEN:12074] array of items to be sorted
*/
long numItemsToSort, /* number of itemsToSort */
long startPosition, [TOKEN:12074] item initially selected */
Move sortMoves[] [TOKEN:12074] 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 2nd item in the list
and move it to the 1st 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 3rd item to the 2nd 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 4th item to the 3rd position, at a cost of 3 more penalty
points. Then the 6th item to the 4th position (cost 5 points), and the 6th item to the
5th 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)