CSE 373: Data Structures and Algorithms
Autumn 1994
Programming Assignment 2
Due at the start of class on Monday November 21.
Write two routines that sort arrays of integers. The first
routine should implement insertion sort. The second routine
should implement quicksort with a median-of-three pivot.
Write a third routine that verifies that an array of integers is
sorted -- just checks the array and says "OK" if it passes
muster.
Run the insertion sort routine on an array of 1,000 integers, and
on an array of 10,000 integers. Verify the result in each case.
(If, for some reason, 1,000 and 10,000 turn out to be
inappropriate choices -- if your routine is "too fast" or "too
slow" -- choose different values.)
Run the quicksort routine on arrays of 1,000, 10,000, and 100,000
integers. Verify the result in each case. (The same comment
applies.)
Modify the quicksort routine so that it "quits" when it gets down
to some number of elements M -- simply returns, rather than
completing the sort by recursing down to the level of single
elements -- and completes the sort by invoking the insertion sort
routine a single time on the full array as a final step. Run
this hybrid sorting routine on an array of 100,000 integers for
M=20 and verify the result. Then try experimentally to find a
value of M where the performance of this hybrid routine is better
than that of "pure" quicksort. (As above, if 100,000 is "wrong",
change it.)
Details
Your input array should be filled with random integers. A C
subroutine that you can use as the basis of this is attached.
(This is a free-standing program; I intend not that you'll use it
literally, but rather that you'll use it as a general model for
what you incorporate in your programs.) It generates random
integers in the range [0 ... 1,000,000]. There will be some
duplicates, but that's no problem. If you use the same "seed",
you'll get the same sequence of random numbers.
Performance should be assessed in terms of CPU time, measured
using the "clock" call. Type "man 3 clock" to learn exactly what
this call does. A C subroutine that you can use as the basis of
this is attached. (See the comment above.) Do *not* count the
time to create the input array. Call "clock" once this is done --
at the instant you enter the sort routine. Call "clock" again the
instant the sort is done -- before you call the verify routine.
Print the results of the second call.
Submission
You should turn in:
- code for all three sorting routines and the verify routine
- output from the six principal runs showing timing information
and the result of verification
- a discussion of the running time behavior of all routines, and
of your attempts to optimize the performance of the hybrid
routine
Random number routine
#include <stdlib.h>
#define MAXINT 2147483647
#define scale (MAXINT/1000000)
#define uniform (random()/scale)
main (argc, argv)
int argc;
{
long random();
int NSAMPLES, numsamples, seed=1;
printf ("Enter a random five-digit number: ");
scanf ("%d", &seed);
printf ("Enter the number of random numbers to be generated: ");
scanf ("%d", &NSAMPLES);
srandom(seed);
for (numsamples=0; numsamples < NSAMPLES; ++numsamples)
printf ("%d\n",uniform);
}
Timing routine
#include <time.h>
runloop(interations)
int interations;
{
int j=0;
while( j < interations ) {
j++;
}
}
main(argc, argv)
int argc;
char *argv[];
{
clock_t CPUtime;
/* Make initial call to clock */
CPUtime = clock() ;
/* Do something */
runloop(atoi(argv[1]));
/* Make second call to clock */
CPUtime = clock();
/* Convert to milliseconds and print */
printf("%d ms. CPU\n",CPUtime/(CLOCKS_PER_SEC/1000));
}