Espresso: A Concentrated Introduction to Java

Laboratory: Sorting

Summary: In this laboratory, you will explore the running time of a variety of sorting routines.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Analyzing the Analyzer
  • Exercise 2: Predicting Running Time of Insertion Sort
  • Exercise 3: Predicting Running Time of Merge Sort
  • Exercise 4: Observations of Quicksort
• For Those with Extra Time

Required code files:

• OutOfPlaceVectorSorter.java
• OOPVSAnalyst.java
• IntegerComparator.java
• InsertionSorter.java
• SelectionSorter.java
• MergeSorter.java
• Quicksorter.java
• AnalyzeInsertionSorter.java
• AnalyzeSelectionSorter.java
• AnalyzeMergeSorter.java
• AnalyzeQuickSorter.java

Exercises

Exercise 0: Preparation

a. Create a package named username.sorting.

b. Copy all of the files mentioned above into that directory.

c. Rename the package in all of those files.

d. Verify that the files compile.

Exercise 1: Analyzing the Analyzer

Look at the source code of OOPVSAnalyst.java.

a. Explain the general purpose of the class.

b. Explain the purpose of the optional parameter to the class constructor.

c. Sketch a typical call to this class that we would use to test the sorting routine from InsertionSorter.

d. Look at the source code of AnalyzeInsertionSorter.java. How does the call differ from your answer to c?

e. Compile and run AnalyzeInsertionSorter.java to run ten trials on a vector of 100 elements and get the average running time.

Exercise 2: Predicting Running Time of Insertion Sort

a. Using AnalyzeInsertionSorter run tests on vectors of 10, 50, 100, 200, 500, and 1000 elements (and any other size vectors of size less than 1000 you deem appropriate).

b. Using those results, write a function that describes the running time of InsertionSorter

c. Test the accuracy of your function on a vector of size 10,000.

Exercise 3: Predicting Running Time of Merge Sort

a. Using AnalyzeMergeSorter run tests on vectors of 10, 50, 100, 200, 500, and 1000 elements (and any other size vectors of size less than 1000 you deem appropriate).

b. Using those results, write a function that describes the running time of MergeSorter

c. Test the accuracy of your function on a vector of size 10,000.

Exercise 4: Observations of Quicksort

a. In our discussions of Quicksort, we noted that Quicksort is likely to run quickly, but is not guaranteed to do so. Using AnalyzeMergeSorter and AnalyzeQuicksorter, see whether the variation in running time for Quicksorter seems to be greater than that for MergeSorter.

b. In our discussions of Quicksort, we also claimed that Quicksort is likely to be the fastest sorting routine. Do your observations confirm that result? If so, how much faster is the average run of Quicksort compared to the average run of Merge sort?

For Those with Extra Time

Implement bubble sort and analyze its running time.

History

Friday, 6 May 2005 [Samuel A. Rebelsky]

• Designed lab. Wrote code.

Monday, 9 May 2005 [Samuel A. Rebelsky]

• Wrote lab.
• Released.