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));
  }