Outcomes Addressed

• apply asymptotic time complexity analysis to choose among competing algorithms.
• implement sorting algorithms such as heapsort and quicksort.

Team Assignment

Students should work with their assigned partner(s) on this assignment.

Overview

This lab assignment is designed to provide insight into the implementation of various sorting algorithms and generic algorithms.

Problem Statement

You must implement three sorting algorithms (they should have the same interface as the Collections.sort(List<T> list) algorithm). You must implement InsertionSort, QuickSort, and MergeSort.

The sorting algorithms should work on any List<T> where T implements the Comparable interface.

In addition, you must write a test program that sorts the words in words.txt. The program should compare all of your sorting algorithms as well as the Collections.sort(List<T> list) algorithm on the following two containers: ArrayList<String> and LinkedList<String>.

Intermediate Deliverable (due one hour prior to week 4 lab)

You must be prepared to demonstrate benchmarking the Collections.sort() method and your implementation of InsertionSort.

Lab report (due 11:00pm, Monday of week 5)

Here is a template file to use as a starting point for this report.

Your report must include:

• A table with the time results of the comparisons
• Discussion containing:
  • A comparison between the different sorting algorithms (including asymptotic analysis of each algorithm)
  • Any problems you encountered (and how they were overcome)
  • Etc...
• Conclusions (what you learned, suggestions of how the lab could be improved, things you would have done differently, etc.)
• Documented source code

As with any report you submit, correct spelling and grammar are required. In addition, your report should be submitted electronically following the Electronic submission guidelines. (You may wish to consult the XML help video and/or sample report before submitting your report.) Be sure to keep copies of all your files, in case something gets lost.

Acknowledgment

This laboratory was developed by Dr. Chris Taylor.