CS209 lab2

CS209 lab2

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l2.html

For this lab you should submit all source code (C files), and the result(s) of running the program on (a few) test cases. The source code must be well presented (indenting, spaces, reasonable variable/function names, etc.) and must include comments (as a rough guideline - aim to have nearly as many comments as lines of code).
The above material should be uploaded to BLACKBOARD before the deadline of 5pm Wednesday 9th. February 2011. You will lose 20% for each day (or part of day) the lab is late.
Plagiarism (the unattributed copying of work from other sources (internet, fellow students,....)) will not be tolerated. Please see http://www.nuigalway.ie/engineering/documents/plagiarism_guide_students _v4.pdf. You risk getting zero for your lab if it is found to be plagiarized.

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/

Consider the QUICKSORT algorithm covered in lectures, with code http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/qs.c Adapt this code

To sort a random list of 1,000 integers between 1 and 1,000,000.
To print out (to the screen) the number of comparisons made (in a sort of 1,000 integers between 1 and 1,000,000). (The relevant lines of code are while(arr[j] > z) and while( arr[i] > z)). Run this a few times.
To print out (to the screen) the number of times the actual function quicksort is called.

Adapt the program http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/ms.c so that it (merge) sorts a random array of NUMINT integers, each between 1 and MAXINT (using rand as in the qs.c program).

For this program print out to the screen

how many times function merge is called
how many times function mergesort is called
how many comparisons in total are made (the relevant line is if a[i] < a[j] ).