Programming Data Structures Assignment 3

Assignment 3 is a search/sort comparison
program.  Your program should read in
words from files called As3Small.txt and As3Large.txt (file to use chosen by
the user).  You are to provide one small
file and one large file (you decide how big and small the files should be and
discuss in your report - will give a good idea of how you think about
testing your program).  You can put the
words all on the same line or on multiple lines.  It doesn’t matter which way you choose, just
document your reasoning behind the decision. 
For multiple occurrences of words, keep track of how many times the word
appears in the file.  Do not have
multiple occurrences of words in your array. 
The number of occurrences of words should be printed out if a word is
found in a search.


For the program, have a menu that will
allow the user to see a comparison table for either sorts or searches, an
option to run one specific sort, an option to run one specific search, and an
option to quit.  The table option should
run all the sorts or searches (with searches, ask the user to enter a word to
search for) and print the following information for each search or sort:


Sorts:   Which

No. of

of Swaps

taken to complete sort

Search:             Which Search

No. of Comparisons

                        Whether it was found or not

                        Time taken to complete search

of Occurrences of a word


Be aware that the user should have a choice
to see the sorts or searches, but not both. 
Also, allow the user to select the file to run the comparison
against.  Be careful not to run the
different sorts on a sorted array and also don’t include loading from file in
the time taken.


The other options should allow the user to
run a single sort or search.  For a sort
on the small test file, the user should see the progression lines like what we
put on the board. Again, the user should be able to select which file to use.  Be aware that if you show progression lines
on the large file, it will take a long time and be very confusing output.  Progression lines should not be shown when doing the comparison option.


The sorts that you should include are
selection, insertion, bubble, merge, and quick. 
As for searches, include linear, binary, and quadratic.  Be sure to think through what would be the
most user friendly for all of this to work and is the most efficient for the


In addition to your program, you should
include, attached to the coversheet, a performance analysis for the sorts and
searches.  You should compare and
contrast their performance in real-time compared to worst case.  The results from your tests using both the
small and large files should guide you in your analysis and conclusions.  You might want to play around with different
configurations of unsorted data. 
Ultimately you should have a clearer of picture of when each sort and
search should be used and be able to articulate why.


Make sure you comment your classes.  When you are finished, upload the java files,
your 2 test files, and your report to the Assignment Drop-box.  Be sure to attach your performance analysis
report to your signed coversheet and turn both of them in.  The program is at the beginning of class on
Powered by