CMSC 162 -- Lab 4

Lab 4

Getting Started

Log onto a computer science server making sure to change the port number.

Follow these instructions to get your files ready to start lab.
  • Use wget to download the file at http://cs.longwood.edu/courses/cmsc162/f18/files/lab4.tgz
  • Uncompress the lab4.tgz file by using tar -xvzf lab4.tgz
  • Use ls to see that there is a new directory called lab4
  • Use cd lab4 to change directory to the lab4 directory

The Problem

We have talked about Big O notation as a theoretical way to compare algorithm run times. In this lab we will compare actual run times.
  1. modify code to count number of comparisons
  2. modify code to take timing information

Implementation

You have been given a file named sorts.cpp which contains almost all of the code you will need.

  • You will need to modify the main function.
  • Add the ability to time the four sorts. Each sort should be run on the same unsorted vector.
  • Construct a table showing the times for the different sorts for different size vectors.
  • Modify the four sort functions to return the number of comparisons.
  • Construct a table showing the number of comparisons for the different sorts for different size vectors.
  • In your README, give a brief analysis of the results
Timings:
Size	Ins.	Sel.	Mer.	Qui.
1024	0.004	0.006	0.001	0	
2048	0.013	0.019	0.002	0	
4096	0.047	0.069	0.005	0	
8192	0.193	0.208	0.01	0.001	
16384	0.811	0.824	0.022	0.003	
32768	3.1	2.656	0.046	0.008	
65536	12.261	10.08	0.094	0.02	
Counts:
Size	Ins.	Sel.	Mer.	Qui.
1024	265185	523776	28781	11446	
2048	1039692	2096128	63646	25208	
4096	4150928	8386560	139711	54638	
8192	16848211	33550336	303952	139944	
16384	66592925	134209536	657080	359932	
32768	267547703	536854528	1412182	937162	
65536	1067174897	2147450880	3020855	3016888	
	

Handin

When you are done you need to hand in your lab. The easiest way is to type make handin.

You lab is due at 11:59pm Sept. 18th 2018.