5
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.