APS 105 - Computer Fundamentals

Lab #7: Searching and Sorting

Fall 2000

You must submit this lab by 11:59pm Wednesday, November 8.

 

1. Objective

The objective of this lab is to experiment with searching and sorting algorithms. You will learn about their running time when given different types of input (sizes and perhaps presorted data).

2. Sorting Arrays

You must write two sorting algorithms to sort an array of strings. The algorithms you must choose from are:

• a slow algorithm, one of either bubblesort or selectionsort
• a fast algorithm, one of either mergesort or quicksort

Be sure to use the following method definitions in your code:

public static void slowSort( String[] array )
public static void fastSort( String[] array )

3. Searching Arrays

You must write a fast (binary) and a slow (linear) searching algorithm to find a given string (the key parameter) and return the index of that string in the array. If no such string exists, return -1.

Be sure to use the following method definitions in your code:

public static int slowSearch( String[] array, String key )
public static int fastSearch( String[] array, String key )

4. Performance

You must measure the performance of your algorithms using two different approaches:

1.

running time in seconds -- since this will vary from run to run, run the program three times and take the average

2.

number of string comparisons done, i.e., the number of times compareTo() is called

Since searching is relatively quick, you must perform multiple searches to produce a runtime significantly greater than zero. Do one search for every single name in the Lab7.fixedNames array, and use the total search time (and the total number of string comparisons). For the binary search, do not include the time or comparisons required to presort the array in your performance results.

For each algorithm you write, measure the performance using four different array lengths: 10, 100, 1000, and 10000 strings. Graph the results against the array length. To keep things simple, these graphs may be hand-drawn.

Notes about Collecting Performance Results

1.

You may create and use a single global class variable,
public static int count;
to count the number of comparisons (but not the running time). Be sure to reset this to 0 before beginning each experiment.

2.

It is preferable to store the result of compareTo in a variable, rather than calling it multiple times. Nevertheless, be sure to properly count every single time the call is executed. Conversely, don't count the times it is not executed.

3.

If your computer takes too long to run using the largest array size, try a smaller value (but larger than 1000).

4.

Use the same computer for all timing measurements.

5.

Make sure no other CPU-intenstive task is running on your computer. Use the top command to see a sorted list of the top CPU hogs (type 'q' to quit top).

6.

Be sure to exclude any time required to generate the names array. Do not include any print statements while doing timing.

7.

For your final submitted code, printing statements should occur only in the main method.

5. Further Exploration

This section is optional. Do it for fun, not marks. Do not include this code or results in your submission.

Try and generate two sets of curves for each sorting method: one that is computed using a fresh copy of the array, and one using a pre-sorted copy of the array.

For the pre-sorted results, do not include the runtime or comparisons needed to do the initial sort.

Try the different variations of bubblesort, quicksort, and mergesort.

6. Helper code

Code is provided in /share/copy/aps105/Lab7.java or at location
http://www.ecf.utoronto.ca/~aps105w/labs/7/Lab7.java

Compile this program and keep it as a separate class from your code. Feel free to use any of the public methods and fields that it contains.

A short description of the public members in the Lab7 class is provided below. There are methods to generate a large array of strings containing names, possibly including random ``words.'' It also includes a fixed array of names, and code to print an array of strings or calculate running time for you.

• String[] genNameList( int length ) returns an array of names of the required length, containing the strings in fixedNames and possibly random ones as well.

• String[] genNameList( int length, String[] userNames ) returns an array of names of the required length, containing the strings in userNames and possibly random ones as well. Use this if you wish to provide your own array of names as a test case.

• String[] fixedNames an array of names that will be used in the generated name list. You can use names in this names array to search for specific names in the generated name list.

• void printNameList( String[] names ) prints an array of strings (probably containing names).

• void startTimer() starts the stopwatch timer for you (it resets the time to zero).

• double getTimerSeconds() returns the number of seconds elapsed since the timer was started.

7. What to submit

• Submit all of your code in a single file/class SearchSort.java.
• Be sure to remove all print statements (except those in your main method).
• Do not use any Stdin methods in your submitted code, and do not submit Stdin.java.
• Do not submit Lab7.java, since we will provide our own for testing.
• Hand in a single sheet of paper with your results (see below) in your tutorial.

computer.ecf% submitaps105f 7 SearchSort.java

For your performance results, hand in a single sheet of paper containing exactly the following:

• Name,
• Student Number,
• ECF LoginID,
• Instructor Name, and
• your performance results.

Your performance results will consist of multiple graphs. Very briefly describe how to read each graph, what you have measured, and how to interpret the results. Write a conclusion suggesting the best algorithms to use.

Since there are nearly 400 students, any folders, binders, report covers, cover pages or additional pages, etc., will simply be thrown out. Please submit only a single page.