17
for class on Tuesday April 7, 1998
Please read Sections 7.5 and 7.6 of the Schneider and Gersting text, and be prepared to discuss the following:
The lab next week (week of April 13) involves sorting, so we'll look again at this important class of algorithms. Remember that shelf of shampoo bottles? Suppose you want to do something like bubble-sort: starting at the extreme left end of the shelf, you'll swap adjacent bottles if the left-hand one's price is larger than the right-hand one's. You continue rightwards until the largest price bottle is at the extreme right. But then, rather than walk all the way back to the left end of the shelf, you swap as you go leftward, exchanging adjacent bottles if they are out of order.
It's not hard to see that after your first two sweeps--one leftward and one right--the most expensive bottle is at the right end of the shelf and the cheapest is on the left end. So if you go again, starting at position 2 this time and ending at position n-1, you'll put the second-most expensive and the second-cheapest bottles in their proper places. Keep going, and the shelf will eventually be sorted.
OK, so please program this algorithm in C. You'll want an outer while loop that keeps you going, and two inner for loops, one for each direction. When you want to swap two array elements, use the following C procedure:
void swap(int A[], int j, int k) {
int temp;
temp = A[j];
A[j] = A[k];
A[k] = temp;
}
Never mind about the ``void''. You can use the swap
procedure as follows: suppose you have an array called
Prices and you want to swap elements i and i-1.
You just say swap(Prices, i, i-1). Note that the
names of variables inside the swap program are
not used outside swap. When you use swap, the first
variable in your list (Prices in the example) is
connected to swap's array A, the second variable in your list
is connected to swap's integer j, and the third to swap's
integer k. We will discuss your programs and also
discuss the use of procedures and functions.