Sorting and Analysis Exercises
COM 1201 – Spring 2003 – Jeff Raab
Introduction
In this exercise set you will write code that implements sorting algorithms, and perform analysis exercises. You must follow the course guidelines for type- or handwritten answers, diagrams, and writing code, as posted on the course website.
Written exercises 1
Perform these written exercises first as practice.
1. Perform exercise 1 on page 123 of the textbook.
2. Perform
exercise 2 on page 124 of the textbook.
3. Perform
exercise 4 on page 124 of the textbook.
4. Perform
exercise 5 on page 124 of the textbook.
Programming exercises
To complete this portion of the exercise set you must download the files from the course website. These files represent a complete CodeWarrior project that will work as-is in the computer labs in Cullinane Hall. If you wish to work at home, elsewhere, or using an IDE other than CodeWarrior, it is your responsibility to configure the software.
5. Write a class named InsertionSort that implements the given ISort interface and performs the insertion sort algorithm. You may use the insertion sort code on page 103 of the textbook as a guide, but you must write a helper method named insert to do the work of inserting each object into its proper location. Test your class in the same way that the given SelectionSort class is tested.
6. Write a class named MergeSort that implements the given ISort interface and performs the merge sort algorithm. You may use the merge sort code on page 108 of the textbook as a guide. Test your class in the same way that the given SelectionSort class is tested.
7. Add
code to the addSorts
method of the SortFactory
class that adds objects of type InsertionSort
and MergeSort
to the SortAnalyzer
taken as input to that method. Use the
given code that adds a SelectionSort
object as an example of how to do this.
Written exercises 2
8. Perform
asymptotic analysis of the insertion sort algorithm as you implemented it in
the InsertionSort
class. In your analysis, use the
variable n to represent the number of
objects to be sorted.
9. Perform
asymptotic analysis of the merge sort algorithm as you implemented it in the MergeSort
class. In your analysis, use the
variable n to represent the number of
objects to be sorted.
10. Run the SortAnalyzer by clicking the corresponding button in the application. Analyze the sort algorithms for each of the three types of data ordering (random, sorted, and reversed) and take a screen snapshot of each resulting graph.
11. Using the screen snapshots you made for problem 10 as a guide, what data ordering is the worst case for the InsertionSort algorithm?
12. Why does the SelectionSort algorithm have the same performance for all of the different data orderings?
13. Which sort algorithm has the best performance in its worst case of the 3 data orderings?
Extra credit
E1. Write a class named MergeSort3 that implements the given ISort interface and performs the merge sort algorithm by splitting the data into 3 parts, instead of 2. Test your class in the same way as the other sort algorithms. Perform asymptotic analysis of the MergeSort3 algorithm as you implemented it. In your analysis, use the variable n to represent the number of objects to be sorted. Add code to the addSorts method of the SortFactory class that adds an object of type MergeSort3 to the SortAnalyzer taken as input to that method. Comment out the appropriate lines so that the InsertionSort and SelectionSort algorithms are not added anymore. Run the SortAnalyzer by clicking the corresponding button in the application. Analyze the two merge sort algorithms for each of the three types of data ordering (random, sorted, and reversed) and take a screen snapshot of each resulting graph. Which merge sort algorithm is better?
Submission
You must submit the following written and/or printed material:
• Type- or handwritten answers to written problems
• Printouts of classes and tests you wrote for programming problems
• Printout of your screen snapshots of the analysis results (Black and white is fine)
You must submit the following electronic material:
• A folder containing all of the provided files in the exercise
• Classes and tests you wrote for programming problems
• Microsoft Word document containing your screen snapshots
Details for electronic submission are given on the course website.