All people taking part in this laboratory must use the laboratory machines
to make the timing comparisons valid.
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.
- Experiment with sorting data by using well known algorithms and data structures.
- Learn more about vectors, lists, multisets, and priority queues.
- Learn a little about the <ctime> library.
[ http://www.cplusplus.com/reference/clibrary/ctime/ ]
(Sort array using STL sort):
[ timeArraySort.cpp ]
[ timeBubbleSort.cpp ]
(Linked Insertion Sort):
[ timeInsertionSortLinked.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 ]
[ 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.
To put up on the board a table and a graph of times for
different ammounts of data for different sorts.
- Choose one of the above algorithms to experiment with.
- Download it, compile it, fix it,and run the result.
- Note down the output: algorithm, size of data, and mean time.
- Experiment with at least 4 other Sizes. Don't forget to note the results on paper.
- Transfer your results on the white board.
- Repeat with a different program....
- The teacher will start plotting points and drawing graphs the data comes in...
. . . . . . . . . ( end of section Process) <<Contents | End>>
. . . . . . . . . ( end of section CSci202 Laboratory 08 Timing Sorting Algorithms) <<Contents | End>>
- 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.
- Algorithm::=A precise description of a series of steps to attain a goal,
[ Algorithm ]
- class::="A description of a set of similar objects that have similar data plus the functions needed to manipulate the data".
- constructor::="A Function in a class that creates new objects in the class".
- Data_Structure::=A small data base.
- destructor::=`A Function that is called when an object is destroyed".
- Function::programming=A selfcontained and named piece of program that knows how to do something.
- Gnu::="Gnu's Not Unix", a long running open source project that supplies a
very popular and free C++ compiler.
- mutator::="A Function that changes an object".
- object::="A little bit of knowledge -- some data and some know how". An
object is instance of a class.
- objects::=plural of object.
- OOP::="Object-Oriented Programming",
Current paradigm for programming.
- Semantics::=Rules determining the meaning of correct statements in a language.
- SP::="Structured Programming",
a previous paradigm for programming.
- 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.
- Syntax::=The rules determining the correctness and structure of statements in a language, grammar.
- Q::software="A program I wrote to make software easier to develop",
- TBA::="To Be Announced", something I should do.
- TBD::="To Be Done", something you have to do.
- UML::="Unified Modeling Language".
- void::C++Keyword="Indicates a function that has no return".