[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [CSci202] / lab07
[Text Version] [Syllabus] [Schedule] [Glossary] [Resources] [Grading] [Contact] [Question] [Search ]
Notes:                    
Labs:          
Thu May 5 11:03:37 PDT 2011

# CSci202 Laboratory 08 Timing Sorting Algorithms

## Purpose

1. Experiment with sorting data by using well known algorithms and data structures.
3. Learn a little about the <ctime> library. [ http://www.cplusplus.com/reference/clibrary/ctime/ ]

## Requirement

All people taking part in this laboratory must use the laboratory machines to make the timing comparisons valid.

## Givens

The following programs all create a either an array or a vector of integers and sort them. They repeat this 100 times (constant Sample) with different random data and calculate the average time.
(Sort array using STL sort): [ timeArraySort.cpp ]
(Bubble Sort): [ timeBubbleSort.cpp ]
(Sort a list in the STL): [ timeListSort.cpp ]
(Using a multiset to sort data): [ timeMultisetSort.cpp ]
(Using a priority queue to sort): [ timePriorityQueueSort.cpp ]
(Selection Sort): [ timeSelectionSort2.cpp ]
(The STL Vectore sort): [ timeVectorSort.cpp ] (in alphabetical order).

Each has something deleted marked like this /******/ that you must find, think about, and replace by the correct information.

## Goals

To put up on the board a table and a graph of times for different ammounts of data for different sorts.

## Process

1. Choose one of the above algorithms to experiment with.
3. Note down the output: algorithm, size of data, and mean time.
4. Experiment with at least 4 other Sizes. Don't forget to note the results on paper.
5. Transfer your results on the white board.
6. Repeat with a different program....

7. The teacher will start plotting points and drawing graphs the data comes in...

### Do not leave until dismissed

. . . . . . . . . ( end of section Process) <<Contents | End>>

## Note -- Quiz 4 and the final may test your knowledge of these programs

. . . . . . . . . ( end of section CSci202 Laboratory 08 Timing Sorting Algorithms) <<Contents | End>>

# Glossary

1. accessor::=`A Function that accesses information in an object with out changing the object in any visible way". In C++ this is called a "const function". In the UML it is called a query.
2. Algorithm::=A precise description of a series of steps to attain a goal, [ Algorithm ] (Wikipedia).
3. class::="A description of a set of similar objects that have similar data plus the functions needed to manipulate the data".
4. constructor::="A Function in a class that creates new objects in the class".
5. Data_Structure::=A small data base.
6. destructor::=`A Function that is called when an object is destroyed".
7. Function::programming=A selfcontained and named piece of program that knows how to do something.
8. Gnu::="Gnu's Not Unix", a long running open source project that supplies a very popular and free C++ compiler.
9. mutator::="A Function that changes an object".
10. object::="A little bit of knowledge -- some data and some know how". An object is instance of a class.
11. objects::=plural of object.
12. OOP::="Object-Oriented Programming", Current paradigm for programming.
13. Semantics::=Rules determining the meaning of correct statements in a language.
14. SP::="Structured Programming", a previous paradigm for programming.
15. STL::="The standard C++ library of classes and functions" -- also called the "Standard Template Library" because many of the classes and functions will work with any kind of data.
16. Syntax::=The rules determining the correctness and structure of statements in a language, grammar.
17. Q::software="A program I wrote to make software easier to develop",
18. TBA::="To Be Announced", something I should do.
19. TBD::="To Be Done", something you have to do.
20. UML::="Unified Modeling Language".
21. void::C++Keyword="Indicates a function that has no return".