[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [CSci202] / lab07
[Text Version] [Syllabus] [Schedule] [Glossary] [Resources] [Grading] [Contact] [Question] [Search ]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Labs: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10]
Thu May 5 11:03:37 PDT 2011

Contents


    CSci202 Laboratory 08 Timing Sorting Algorithms

      Purpose

      1. Experiment with sorting data by using well known algorithms and data structures.
      2. Learn more about vectors, lists, multisets, and priority queues.
      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 ]
      (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 ]
      (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.
      2. Download it, compile it, fix it,and run the result.
      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".

End