Class Crib Notes for CPSC 110 Brent Dingle

Friday, April 5, 2002

Reminders:

Assignment 6 – do NOT use arrays (even though we talk about them today), begin working on it now if not already.

Quiz 5 is Wed April 10

Don’t forget to write up the CS history report.

Last time:

Chapter 9 – arrays and strings

Notice there are some built in functions that operate on strings. Look them up.

Minimally understand and be able to use:

pos, delete, insert, length, copy, upcase

I suggest writing practice programs to see what they do and how to use them.

Remember strings indexing starts at ONE!

Today:

Chapter 10 – sorting

Effectively what is about to be presented is based on a Bubble Sort

Below is the Pseudo Code to sort items on shelves

- say each shelf had fruit on it

- and you wanted to alphabetize the fruits by shelf

- so apples are on the top shelf

- bananas are on the next shelf

- oranges are somewhere in the middle, etc

PROCEDURE SortThem(VAR shelf : WHATS_ON_SHELF_TYPE);

VAR

i, k : integer;

BEGIN

for i := 1 to NUM_SHELVES do

BEGIN

for k := i + 1 to NUM_SHELVES do

Begin

if (contents of shelf[ k ] < shelf[ i ]) then

begin

Exchange(shelf[i], shelf [k]);

end

End { for j }

END { for i }

END;

So the picture might be:

Shelf 1: Oranges

Shelf 2: Apples

Shelf 3: Bananas

The algorithm would first exchange Oranges with Apples:

Shelf 1: Apples

Shelf 2: Oranges

Shelf 3: Bananas

Then the algorithm would first exchange Oranges with Bananas:

Shelf 1: Apples

Shelf 2: Bananas

Shelf 3: Oranges

And then the algorithm would be done.

Try doing the same thing with names on a shelf.

Assume the initial order is:

Shelf 1: Bob

Shelf 2: Jonathan

Shelf 3: Jane

Shelf 4: Curly

Shelf 5: John

Shelf 6: Karla

Shelf 7: Christina

Shelf 8: Snoopy

Shelf 9: Alice

Shelf 10: Ann

Shelf 11: Paul

Shelf 12: Mary