MCS-177 Project: Timing Card Sorting
To be done in lab: March 4, 2003
MCS 177: Computer Science I, Spring 2003
Problem:
What is a good algorithm for sorting a set of cards? In this project,
you will compare the speeds of two different methods for sorting numbered
cards by doing the card-sorting experiment described in section 4.1 of
the book. Be sure to read through the beginning of this section before
coming to lab, in particular the sidebars on pages 77-79 describing the
two sorting algorithms. You will not have to hand in a lab report, and
we will discuss the results of the experiment in class.
In Lab:
Instead of using physical cards to do your sorting, you will use
simulated cards, in the form of a pair of Java applets. In order to use these
applets, you will first need to "enable Java" in Netscape. This is
done by selecting "Enable Java" under the "Advanced" category in your
preferences; you can get to your preferences by selecting the
"Preferences ..." sub-item in the "Edit" menu in Netscape. If you have
any questions about this, ask your lab instructor.
After enabling Java, go to the Card
sorting simulations webpage, which is linked from the web version
of this handout. We give instructions there about how to
run the applets, and we will demo them in lab anyway. We want you to do
selection and mergesort with 4, 8, 16, and perhaps 32 cards (32 with selection
sort is painful). Please record your times in a table in order to report
them to the lab instructor.
When you are done sorting 4, 8, 16, and 32 cards using each of the two
sorting algorithms, bring your times to the lab instructor for
incorporation in the class-wide graph. If you run out of time without
getting all eight timings done, don't worry about it--depending on how
many false starts you have until you get the hang of the two sorting
algorithms, and how speedy you are with the cards, you might not get
all eight done, but you'll no doubt still get the main point of the
exercise.