CS286 -- Lab 2: Sorting



->Courses
->CS286
-->Homework
-->Lab 1
->Lab 2
-->Lab 3
-->Lab 4
->Electronic Submission
->Old Exams
->C++ Examples
->MSVC++ Info
->STL Info
->MFC/GUI Info
->Software
->Tentative Schedule
->Support Forum
->Course Policies

[Courses]
[Rich][Home][Rich]
[PHome]

Spring Quarter 2003

Objectives Addressed

  • Be able to use generic algorithms from the STL and implement additional generic algorithms.
  • Be able to apply asymptotic time complexity analysis to choose among competing algorithms.
  • Understand how sorting algorithms such as heapsort and quicksort work.

Purpose

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

Assignment

You should implement three generic sorting algorithms (they should have the same interface as the generic sort algorithm). You should implement InsertionSort, QuickSort, and a hybrid sort that uses QuickSort on any partition with more than 20 elements and InsertionSort for partitions with 20 or fewer elements. One algorithm should require only bi-directional iterators while the others may require random access iterators.

The sorting algorithms should work on any container (with the appropriate iterators available) containing any type of object for which the less than operator is defined.

In addition, you should write a test program that sorts the words in words.txt. The program should compare all of your sorting algorithms as well as the generic sort algorithm and the list's sort algorithm (be sure to fix it first) by exercising all of them. You may find the benchmark class useful in your comparisons.

Lab report (due 11:00pm, the day prior to week 6 lab)

Each pair should submit one lab report. Your report should include:

  • A table with the time results of the comparisons
  • Discussion (comparison between the different sorting algorithms, your experience/impressions of the CSP, how you an your partner worked together, any problems you encountered, etc...)
  • Conclusions (what you learned, suggestions of how the lab could be improved, things you would have done differently, etc.)
  • CSP spreadsheet (Use naming convention: 286MSOEloginL2.xls. Begin with a new spreadsheet. Use your best judgement in establishing an initial baseline based on the PSP data from each of you individually. Be sure to justify your methodology for establishing your baseline.)
  • You may enter data into the XML formatted Activity and Defect logs or submit an additional spreadsheet with this data. (Use naming convention: 286MSOEloginL2b.xls)
  • Documented source code

Template Lab Report

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 sample report before submitting your report.) Be sure to keep copies of all your files, in case something gets lost. It may be wise to keep a diskette backup as well.

If you have any questions, consult the instructor.

© 2001-2003 Dr. Christopher C. Taylor Office: CC-27C Phone: 277-7339 Last Updated: Mon Mar 31 08:13:06 2003
I am responsible for all content posted on these pages; MSOE is welcome to share these opinions but may not want to.