Fifth Assignment, due 7th November
2002
Electronic Submission, hw5
(I knew Thursday was the 7th. Why did I let you persuade me
it would be the 6th? How could you all be so sure it would be
the 6th anyway? Was it mass hysteria or some kind of conspiracy?)
Write a program that reads words (up to a maximum number selected by the user)
from a plain text file, then sorts the words, and displays the time it took
to perform the sort.
There is a specially prepared text file, containing all the words from Alice
in Wonderland, but with all punctuation except for apostrophes removed. Use
this file for your tests. The unix shell knows the file as ~data/alice.txt
from whence you may copy it into your own directory. If you wish to open
the file without first copying it, the full path as understood by fopen()
is "/usr/home/users/data/alice.txt".
For a reminder of how to accurately time a running program, follow
this link. As promised, I have provided
a more accurate timing function that only measures CPU time expended
on your program, not normal elapsed time. The function in this
link is tested and works on rabbit; you may copy and paste it into
your own programs.
Once you have a working progrm producing believable times, run it with a
selection of different data sizes (i.e. tell it to read a different maximum
number of words each time before sorting), and plot a graph showing how
time varies with data size. Try to work out a formula that would allow the
expected run time to be calculated from a known number of words. You may
use a graphics program to create a .gif or .jpg file containing your graph,
or you may draw it on paper and turn it in by hand. Paper graphs will not
be considered late if given to me the next time class meets after the due
date. The program itself must still be submitted on time.
The sample text file contains 26,347 words, so you can't run tests on a
data size greater than that. Which is not a problem; 26347 is quite big enough.
This is a sample of what a run of your program should look like. You do not
need to follow this format exactly, but do not produce so much output that
the results can not easily be seen.
$ a.out
Maximum number of words to read: 5000
Sorting 5000 words took 0.529 seconds