Homework Assignment 7

Assigned: Monday,Mar 17, 1997.
New Due Date: Monday, Apr 7, 1997.

Read: Read Chapters in the class text, 8, 11, 13 new edition (or Chapters 8, 10 and 15 old edition) and the the class notes on Loop Invariants.

Program: You will write two sorting programs, InsertionSort.C and QuickSort.C and use a suite of increasing sized inputs show how the run time varies with input size for each of the two programs. You are required to submit a plot of your results to complete the assignment.

Your program development must include statement of Loop Invariants for each looping construct in your code. See the class notes on Loop Invariants.

In detail: your program opens a file, reads the number of integers to follow as the first integer in the file, and inputs that many integers, one integer per line from the file. The program places each integer in an array location. There will be no more than 20,000 integers in the file. There is an example of how to input integers from this format of file.

The InsertionSort.C program will sort the numbers in the array by using a while loop whose Loop Invariant is:

The numbers originally in locations 0 through i-1 of the array are now arranged in ascending order in locations 0 through i-1 in the array. Each time through the loop, increase i and restore the loop invariant by placing the new item in its proper place among the other items. Do this by swaping the integer with the integer just before it in the array if they are not in ascending order. You may have to got just until the the integer is in location 0. Overlook this possibility and your program will have a bug.

Then print the array (if it is small), or just the word DONE if the array is large.

The QuickSort.C program acts the same except that Quick Sort is used to sort the numbers. Quick Sort is recursive. It receives an array A and two indices, top and bottom,

Precondition: top <= bottom and sorts the array items between top and bottom, including top but not bottom. Sorting the array of n elements sets top to 0, bottom to n.

To sort A[top] .. A[bottom-1]:

  1. set A[top> as the pivot;
  2. partition the section of the array on the pivot. Suppose the pivot finishes in location i;
  3. recursively call Quicksort for A[top] .. A[i-1] and A[i+1] .. A[bottom-1].
To partion the array region is to establish that all integers found in A[top] .. A[bottom-1] which are smaller than the pivot have been moved to indices less than that of the pivot, and integers found in A[top] .. A[bottom-1] which are larger than the pivot have been moved to indices greater than that of the pivot. Loop Invariant: Integers l, r obey:
  1. top <= l <= r <= bottom
  2. for all j in [top, l], A[j] <= pivot,
  3. for all j in the range (r, bottom), A[j] >= pivot.
(Recall the use of square and round parentheses: [a,b) means that a is in the range, and that b is not.) Each time through the loop, press l to the right and r to the left until they meet. Maintain the loop invariant by swapping integer values when there is a contradiction both due to A[l] being too big (it belongs on the right) and A[r] being too small (it belongs on the left).

You create test input files using the program MakeNumbers.C. Download the source, CC and run the file. It will prompt you for a file name (e.g. input.dat) and the number of integers to generate. Run both programs for time on sample inputs of various sizes, to see how run time varies with size. To time your program, use the Unix command time followed by the command name (a.out), on the same line: 

     appomattox> time a.out
     Sorting 20000 integers.
     Checking.
     0.192u 0.041s 0:00.24 95.8% 0+0k 0+0io 0pf+0w
     appomattox>

Insertion Sort is a O(n^2) algorithm: it should run in time proportional to the number of elements to sort squared. I.e., double the input, quadruple the run time. Quick Sort is an O(n log n) algorithm run slightly more than proportional to the number of elements. I.e., double the input, double (plus a constant bit) the run time.

However each algorithm demonstrates sensitivity to the type of input given. Insertion Sort is as fast as can be on already sorted data. On the contrary, already sorted data turns Quick Sort into Slowest-Sort. The study of algorithms, such as the two sorting algorithms presented in this homework assignment, is a major part of Computer Science. The course mth517 is devoted entirely to the study of algoritms.