Third Assignment, due 21^st February 2002

Electronic Submission, hw3

In the first two assignments, we observed that searching through a large database can take a lot of time. The times you measured may not have seemed very long, but remember we only has a 1000-item database. Real-world databases could easily be many thousands of times as long, and would take correspondingly longer to search.

This assignment is an adaptation of the second assignment. After reading the data file into your array of person structs, you must sort the array into ascending order of the persons name (last name is the primary sorting key, first name is the secondary key, so Jim Ant comes before Arthur Bat, but Jill Ant comes before Jim Ant).

Then when the user requests a search, if the search is based on a person's name, your program should take advantage of the fact that the array is sorted, and perform a very efficient and fast Binary Chop Search. A normal search (usually called Brute Force because it just uses the raw speed of the computer to get the job done, rather than any subtle use of intelligence) would have to perform 1000 comparison operations to search through a database of 1000 entries; binary chop search should be able to do it in 10 comparison operations. If the user requests a search that is not based on a person's name, it will of course have to proceed in the old standard way.

Use the timing functions to find out how long it takes to sort the whole array.