CSC 172
Homework assignment 3

Assigned 25 Feb, 1999
Due 16 Mar, 1999

Searching and Sorting

I assume you've completed homework 2. In this assignment, you'll enhance that program with searching and sorting capabilities.

From Homework 2, you've already got a mechanism for the user to type in a list of names, indicating (by typing "quit" or leaving the name blank or something) when the list is complete. You'll need to use that mechanism several times in this assignment, so you might want to pause at this point and make sure it's properly modularized to avoid duplicate code.

Version 1

After the user has typed in a list of names and you've stored them all in a Vector, we'll start searching for names. Allow the user to type in another list of names; after each one, your program will search through the Vector to find that name, print a message indicating whether and where it was found, as well as how many comparisons it took to find it (or to conclude that it wasn't there).

Version 2

Choose one of the "move to front" strategies in section 10.4 of the textbook and implement it so that if a name has been found recently and is searched for again, the second search won't take so many comparisons. Tell me (and the user) which strategy you chose: move all the way to the front, move up by one place, move halfway up, or some other strategy of your own invention.

Version 3

After the user has finished with this list of names to be searched for, your program should sort the entire Vector in alphabetical order (as usual, look at first names only if necessary to resolve a tie in last names), then allow the user to type in a third list of names. After each one is typed, your program will search through the Vector using binary search to find that name, print a message indicating whether and where it was found, as well as how many comparisons it took to find it (or to conclude that it wasn't there). In this case, don't move things to the front after finding them; that would make the list no longer sorted, so the binary search wouldn't work any more. Note that once the list is sorted, finding the median element (the extra credit from homework 2) is easy.

Hints:

How easy or difficult this assignment is will depend in part on how well you organized homework 2. For example, if you haven't written a NameList class yet, you'll probably want to do so now.
Since you need to search the NameList two different ways, you should probably write two different search methods -- say, linearSearch and binarySearch -- as well as a sort method. Which allows you, if you're into that sort of thing, to find out what happens when you try a binary search on a list that isn't actually sorted.

Examples:

Please type in a list of names.  When you're done, just hit RETURN when asked for another name.

First name?
No first name.  Do you want to enter a last name?no
Thank you.  Here's some information about that list of names.
There were no names in the list.

Now let's search through the list, using linear search.
First name?Joe
Last name?Schmoe
The name "Joe Schmoe" was not found in the list.  It took 0 comparisons.
First name? 
No first name.  Do you want to enter a last name?no

Now let's sort the list and search through it, using binary search.
First name?Joe
Last name?Schmoe
The name "Joe Schmoe" was not found in the list.  It took 0 comparisons.
First name? 
No first name.  Do you want to enter a last name?no

OK, bye now.

Please type in a list of names.  When you're done, just hit RETURN when asked for another name.

First name?Stephen
Last name?Bloch
First name?
No first name.  Do you want to enter a last name?no
Thank you.  Here's some information about that list of names.
The shortest first name was Stephen.
The longest first name was Stephen.
The average length of a first name was 7.0, and no first names were longer than that.
The earliest name in alphabetical order was Stephen Bloch.
The last name in alphabetical order was Stephen Bloch.

Now let's search through the list, using linear search.
First name?Joe
Last name?Schmoe
The name "Joe Schmoe" was not found in the list.  It took 1 comparison.
First name?Stephen
Last name?Bloch
The name "Stephen Bloch" was found in position 0.  It took 1 comparison.
Moving it halfway up....
First name? 
No first name.  Do you want to enter a last name?no

Now let's sort the list and search through it, using binary search.
First name?Joe
Last name?Schmoe
The name "Joe Schmoe" was not found in the list.  It took 1 comparison.
First name?Stephen
Last name?Bloch
The name "Stephen Bloch" was found at position 0.  It took 1 comparison.
First name? 
No first name.  Do you want to enter a last name?no

OK, bye now.

Please type in a list of names. When you're done, just hit RETURN when asked for another name.

First name?Joe
Last name?Schmoe
First name?Stephen
Last name?Bloch
First name?Annie
Last name?Schmoe
First name?Edward
Last name?Beeblebrox
First name?Roddy
Last name?MacDowell
First name?Former
Last name?Prince
First name?Malcolm
Last name?MacDowell
First name?
No first name. Do you want to enter a last name?no
Thank you. Here's some information about that list of names.
The shortest first name was Joe.
The longest first name was Stephen.
The average length of a first name was 5.57, and 3 first names were
longer than that.
The earliest name in alphabetical order was Edward Beeblebrox.
The last name in alphabetical order was Joe Schmoe.

Now let's search through the list, using linear search.
First name?Annie
Last name?Schmoe
The name "Annie Schmoe" was found at position 2. It took 3 comparisons.
Moving it halfway up....
First name?Annie
Last name?Schmoe
The name "Annie Schmoe" was found at position 1. It took 2 comparisons.
Moving it halfway up....
First name?Stephen
Last name?Bloch
The name "Stephen Bloch" was found at position 2. It took 3 comparisons.
Moving it halfway up....
First name?Annie
Last name?Schmoe
The name "Annie Schmoe" was found at position 0. It took 1 comparison.
Moving it halfway up....
First name?Arnold
Last name?Schmee
The name "Arnold Schmee" was not found in the list. It took 7 comparisons.
First name?Former
Last name?Prince
The name "Former Prince" was found at position 5. It took 6 comparisons.
Moving it halfway up....
First name?
No first name. Do you want to enter a last name?no

Now let's sort the list and search through it, using binary search.
First name?Annie
Last name?Schmoe
The name "Annie Schmoe" was found at position 5. It took 2 comparisons.
First name?Annie
Last name?Schmoe
The name "Annie Schmoe" was found at position 5. It took 2 comparisons.
First name?Stephen
Last name?Bloch
The name "Stephen Bloch" was found at position 1. It took 2 comparisons.
First name?Annie
Last name?Schmoe
The name "Annie Schmoe" was found at position 5. It took 2 comparisons.
First name?Arnold
Last name?Schmee
The name "Arnold Schmee" was not found in the list. It took 3 comparisons.
First name?Former
Last name?Prince
The name "Former Prince" was found at position 4. It took 3 comparisons.
First name?
No first name. Do you want to enter a last name?no

OK, bye now.

Last modified: Tue Mar 2 10:17:33 EST 1999

Stephen Bloch / sbloch@adelphi.edu

CSC 172 Homework assignment 3