17
for class on Tuesday April 4, 2000
Please read Sections 7.6 and 7.7 of the Schneider and Gersting text, and be prepared to discuss the following:
The lab next week (week of April 10) 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 idly 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 rightward and one left--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 this time at the second position and ending at the next-to-last, 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 function:
void swap(int A[], int j, int k) {
int temp;
temp = A[j];
A[j] = A[k];
A[k] = temp;
}
Section 7.7.3 should help you understand this. You can use the swap
function 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 swap are private to the swap function; in other words, another function (like your sorting function) can use these same variable names for other purposes, and things will not get messed up.
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 functions.