5

### Reading Assignment and Discussion Topics

Computer Science 111

*for class on Tuesday Feb. 15, 2000*

Please read
Sections 3.1 through 3.3 of the Schneider and Gersting text,
and be prepared to discuss the following:

The text proposes three different algorithms for the
so-called "data cleanup" problem. The first of these
(shuffle left) is obviously a straw-man for the authors'
analysis later in this chapter: they wish to have a really
really inefficient algorithm to contrast with an
efficient one (the converging pointers method).
But notice that the slow algorithm preserves
the original
left-to-right order of the data items in the final list,
whereas the fast algorithm changes the order.

So let's
develop a fourth algorithm for this problem,
one that is faster than
shuffle-left but that preserves the original
order of the nonzero data.
Suppose that each time a nonzero data item
is copied on top of a zero, we replace the original
data item with a zero. In effect, we exchange
the zero and the nonzero data item. Can you use
this idea in a new algorithm? Start with two pointers
at the left end of the list. Move one of them right until
you find a zero; then, using the
other pointer, find the first nonzero item to
the right of that zero and do the exchange.
Continue in this fashion until the entire list has
been processed.

Please write some pseudocode that expresses this algorithmic idea.
We will analyze and compare student solutions during this class.